Wednesday, May 23, 2018

[ouquiwdc] Two Google location codes

It looks like everyone and their mother has invented an alternative to latitude and longitude for specifying a location on Earth.  Google has (at least) 2:

  • Open Location Codes (aka Plus Codes)
  • S2 Geometry (specifying locations as a single 64-bit integer)

[menkqfde] SAT puzzle

CNF satisfiability seems fairly straightforward to present as a visual, electronic puzzle: variables and clauses are connected by lines, possibly with an inverter inserted; variables, lines, and clauses light up when activated.

[nmztynrl] Designed for 3D printed repair

Design a mass-produced product so that repairs to it can be made with a 3D printer.  Are there mass-production materials that mimic the look of 3D-printed materials, so that a repaired portion looks similar to the original?  (Though this could be solved with paint.)

Of course, specifications of the parts need to be made available.

[tpieeufj] Ruler and protractor construction

Although compass and straightedge is elegantly simple, there is also beauty in the power of being able to measure out distances and angles.  (This is, of course, drafting.)  It adds another "dimension" to the drawing, namely, the calculations, possibly very difficult or impressive, done off to the side to obtain the values of desired angles and lengths.

Tuesday, May 22, 2018

[mkthxboj] Dance cipher

We sketch out some ideas for designing a block cipher inspired by moves used in contra dance.

Each person keeps track of one number in their memory, maybe as little as 1 bit of memory.  During the "swing" move, two people meet, tell each other their current number, then compute new numbers to remember based on their old numbers, some relatively simple function computable with mental arithmetic.  (This is a nice example of SIMD parallel computation done by humans.)  It might need to be a invertible function for decryption to be possible (unless part of a larger structure like a Feistel network).

Everything else is permutations of the dancers causing different people to meet, causing mixing.  Various contra dance and contra dance inspired moves available as permutations:

Standard progression: ONEs move one couple down the hall, TWOs up.

Horizontal movement: align the grid of dancers as horizontal sets across the hall and do any of these permutation moves. A simpler variation might only have the couples out at the top execute a horizontal permutation.

Whole set take hands in giant oval and turn the oval.  Traditionally the oval eventually turns back the same amount, but break tradition to allow mixing of distant dancers.  Practically, turning the oval by a constant and consistent amount might be tricky.

Pull by right pull by left around the whole set (grand right left).  Again, seeking mixing with distant dancers.  Not following this move by its inverse (as would be traditionally done) will break up couples: this is a mixer.

Different sets do different permutations.  Maybe one set does oval for 10 counts followed by 6 counts of something else that doesn't travel (e.g., swing), while another set does 8 and 8.  Because dancers move horizontally between sets, they will need to pay attention to where they are to know what to do.

Or, a similar effect as different sets doing different moves could accomplished by simply having sets of different lengths.  When combined with the possibility of horizontal sets, the grid of dancers needs to start out convex, e.g., house-shaped pentagon with the ground at the top of the hall.

The need for these permutations causing mixing with initially distant dancers was inspired by how the rho step of Keccak specifies different bit rotation amounts (triangular numbers) depending on the position of the word within the 5x5 matrix.

All the other contra dance moves (and sequences of moves) which are equivalent to the identity permutation can also be included for aesthetic purposes, e.g., flow.

The dance does not strictly repeat, maybe different global round constants called out on the fly and used in the swing computation.  Or, different rounds correspond to different dances, where people start the next dance exactly where they ended the previous dance.  You can't leave, though you can have a substitute to take your place.

[nidkfbsi] 60 card deck

60 seems an elegant number for cards in a deck as opposed to the standard 52.  4 suits of 15 or 5 suits of 12: can a deck support both?  (Previously, 101 cards.)

5 suits seems more natural with poker's 5-card hands.  The anti-flush becomes possible: 5 cards of different suits.

[lckrdkga] #fucks

"I don't give a fuck."  "I have run out of fucks to give."

The amount of fucks you have available to give is another way that self-qi is popularly expressed.

Previously, spoons.

[raunixym] Derive the number field sieve

Give a mathematically formal description of multiplication to a computer, and have it automatically derive the general number sieve algorithm for factoring.  This seems so difficult as to feel like seeking the Holy Grail, though it is asking a computer to replicate steps previously done by humans.

[tscumkru] Mechanical pi

Turn one knob one revolution and another dial turns exactly pi times.  Build this as a mechanical device so that is it self-evident and understandable that the multiplier really is pi.  Plain gears won't work because only integer ratios are possible with them, and pi is irrational.

Easier might be to turn a knob of diameter D and cause a linear slider to move the distance pi*D.

[ooaoelln] Horizons in games

In a 3D game taking place on a flat world, one needs to artificially impose a far clipping plane to avoid having to render infinite objects.

However, on a spherical world, the surface curves away, limiting the distance to the horizon, though it still might be a lot of area/volume.

[hipjuanm] Finger painting entropy

Draw something on your touchscreen.  Use the image, perhaps also including the timing of the strokes, to seed a cryptographically secure random number generator.

Wednesday, May 16, 2018

[zbsgujnx] Lowercase pi

Here is a page of pi in old-style numerals.  We use text figures, large type, and double-spacing all to make it easier to read.

LaTeX source code.  Also available in the same directory is the square root of 10 written out in the same way.  The square root of 10 seems a more appropriate number to write out in many digits of base 10.

Proportional spacing was accomplished with cfr-lm, but it is not available in math mode.

Monday, May 14, 2018

[tkucddbb] A few monotonically decreasing discrete probability distributions of infinite size

  • Zipf
  • Gauss-Kuzmin, the distribution of simple continued fraction denominators
  • Poisson
  • Geometric distribution (memoryless)

[slqhjfjp] Zipf Huffman

Compute the Huffman tree for a Zipf distribution of various sizes.  Zipf seems to happen often naturally in the world with regards to information.  Particularly useful might be for 256 elements, representing bytes.  Because the Zipf distribution is fixed (e.g., for exponent 1), this needs only to be computed once.  To use it, specify the permutation.

For exponents greater than 1, the infinite tree could be precomputed.  Arithmetic coding might be easier.

[yrznyyze] Octahedron and tetrahedron

The dihedral angle of the regular octahedron and the bond angle of the central carbon atom in sp3 hybridization (e.g. methane, with its hydrogens arranged at the vertices of a regular tetrahedron) are both 109.5 degrees.

Assuming they are the same value, create a geometric demonstration of this, maybe a visual proof.

Saturday, May 12, 2018

[lpmrvuli] Block ciphers as permutations

Given a key, a 128-bit block cipher such as AES does one of the 1.6*10^12963922773915897352139996524992575205380 possible permutations of 2^128 items.  lngamma(2^128+1)/log(10), 10^10^40.1.

Assuming 128-bit key length, only 2^128 = 3.4*10^38 permutations of the gigantic number above are actually possible.  This is a very small fraction.

The simplest possible block cipher would have key-length 43065219282621326757565580404980237828911 bits (lngamma(2^128+1)/log(2)), enough to specify most (71.3%) permutations of 2^128 items.  Add 1 more bit if you want all of them.  This is of course completely impractical: the key would be 5383152410327665844695697550 terabytes.

It does illustrate that, beyond AES-256, there is plenty of room for block ciphers with longer keys if we wanted them.  They would probably only have a security level of (at most) 128 bits: with 2^128 work, we could try every possible input block and record what comes out.  This is much easier than brute-forcing a much larger key.

Previously, on specifying a permutation of (only) 2^8 items.

[dmpvhcjz] Storing a permutation

Consider a storing a permutation of 2^8 = 256 elements.  The easiest way to store it is a byte array of length 256, consuming 8*256 = 2048 bits total.

The densest possible encoding is mixed radix based on the factorial, requiring log(256!)/log(2) = 1683.996 bits.  (The .996 is a nice coincidence.)

A hybrid approach does bit-packing.  The first 128 elements use 8 bits per element, then the next 64 use 7 bits, and so forth.  sum(i=0,7,2^i*(i+1)) = 1793 bits.

Tuesday, May 08, 2018

[nlnquejq] Tiling a circle

Take a section of a tiling, for example a square divided into squares, and morph it into a circle.  The tiles will no longer be congruent.  Which tilings work well?  It depends on the shape of the initial section: one could choose a section that approximates a circle, then morphing (probably) won't cause too much distortion.

Morphing could be done with nodes connected by springs.  Or maybe something that preserves area or incircle of each tile.

Motivation was to create a circular board game (for aesthetic reasons) out of a polygonal one like chess.

[powaoxal] Depression feedback cycle and evolution

If you're sad, no one wants to be friends with you.  If no one wants to be friends with you, you'll become more sad.  Surely this feedback cycle is not new, not just a feature of modern society.

Some amount of those depressed people will commit suicide and not pass along their genes to the next generation.  Or, they will seek out sexual intercourse less frequently, or they will be less desirable, so potential partners will seek them out less frequently.  Or, as social outcasts, their children will receive less support so be less likely to survive until maturity.  Evolution is very sensitive to these effects, especially if given thousands of generations.  So it is very mysterious why this feedback cycle exists, and exists so strongly.

Previously, hypothesizing bipolar.

[yytxjjsk] No word separators in identifiers

When an identifier in computer code is composed of two or more words, consider mashing them together with no separator or camelCase.  The reason is because English (as well as many other languages) has compound words, and, in light of that, "no separator" is easier for the programmer to remember: Is it doghouse or dog-house/dog_house/dogHouse?  In English, something might etymologically start out as 2-word noun phrase, dog house, then gradually morph through dog-house into doghouse.  It's easy for the programmer to remember the two words (as concepts), but harder to remember where in that spectrum the words lie, dictating whether it gets a separator.

One could do a less stringent policy where words of very different grammatical purpose can have separators/camelCase: doghouse_is_darkgreen.  Also, add a separator when there would be confusing ambiguity: experts-exchange.

It might look like German with its long compounds (which has worked fine with no hyphens or camelCase!).  It might be a bit harder to read (a tradeoff in making the code easier to write), but tools can help with reading: maybe a comment where the identifier was declared and hover text (hover-text? hovertext?) over the identifier in use, displaying that comment.

[fjjwhqut] Estimating resistance to invasion

The traditional narrative states that Hitler underestimated the amount of resistance the Soviet Union would put up against invasion: "We have only to kick in the door and the whole rotten structure will come crashing down."

How does one correctly estimate such a quantity?  Exactly where was Hitler's mistake in calculation?  (Was his model wrong?  Or was it poor military intelligence gathering?)  Having learned from past mistakes, do we have better models now?  Obviously, this is a taboo kind of topic, because an accurate model would tell anyone who has it, which countries today are ripe for invasion?

Previously, a nontraditional narrative of Operation Barbarossa.

[lhbibwxj] Build your own hard drive

Build a functioning magnetic storage device from scratch (maybe a kit).  The idea is to do magnetic storage in a way that is completely documented and well understood, at least by you.  This is in contrast to current commercial hard drives, which have inaccessible firmware running on the circuit board of the hard drive itself, so recovering the data from just the pattern of magnetization on the platters is close to impossible.

Magnetic storage has the potential of lasting a very long time, but only if the metadata about how information is encoded in the magnetization is also preserved.

[cbzfknaq] Coprocess idiom

Start a coprocess, and you are returned to a modified shell environment.  You can do all the things that you normally can in the shell environment, plus a few extra things enabled by the coprocess running in the background -- there are commands to interact with it.  The key idea is, you interact with the coprocess in an "open world", not a "walled garden".  When you are done, explicitly kill the coprocess, or exit the shell automatically killing it, freeing the memory and other resources that the coprocess was consuming.

Inspiration was loading a large database into memory, preprocessing it to allow for more rapid queries at the cost of greater memory, then running a bunch of queries against it, interspersed with processing the results of each query.

[cwghwbjg] Casino d30

Casino dice with sharp edges are fair, but the cubes don't roll very well unless flung with considerable velocity on a special table as done in craps.  Rounding off the edges and corners makes them roll better for tabletop games, but it is hard (probably impossible) to round all the edges in precisely the same way to keep a die fair.

Seek the best of both worlds by creating a casino-style die using a polyhedron with a larger dihedral angle. The rhombic triacontahedron (30 faces) seems attractive because with repeated numbers it can simulate a d6 or a d10.

This seems partially already done by GameScience precision dice, but they fail to have the face markings carved out then filled with an ink of identical density, as casino dice do.  Also, another problem of irregular shape found in testing.

Dihedral angles:

  • cube 90
  • octahedron 109
  • dodecahedron 117
  • rhombic dodecahedron 120
  • icosahedron 138
  • rhombic triacontahedron 144

Based on dihedral angle considerations only (so one needs both edge transitivity and face transitivity), for d12, one should prefer rhombic dodecahedral dice if you want them to roll more, or regular dodecahedral dice if you want them to roll less.

[mmpffczs] Generating Keccak round constants

We investigate the round constants for the Keccak hash function (of which SHA-3 is a subset).  We work mostly from the officially published SHA-3 standard which was a little bit easier to understand than the reference specification.

These round constants are used in Keccak's iota step-mapping function.  The internal function rc(t) is a linear-feedback shift register (LFSR) with 8 bits of state and a period of 255.  Its period is 255 if its state is seeded with a nonzero value, which it is, namely the value 1.  Here is its full period, grouped in chunks of 7 for reasons which will be made clear shortly.  We write the 0 bit as period "." and the 1 bit as "1" to be able to easily distinguish them: 1...... .1.11.. .1111.1 ....111 11111.. 1....1. 1..1111 .111... ..11... 1.1.11. .11..1. 111111. 1111..1 1.111.1 11..1.1 .1..1.1 ...1..1 .11.1.. .11..11 1..1111 ...11.1 1....1. ..1.111 .1.1111 .11.111 11....1 1.1..11 .1.11.1 1.1.1.. ...1..1 11.11.. 1..1..1 1...... 111.1.. 1...111 ...

The Keccak round constants are easiest to understand in binary.  We write binary constants below with the least significant bit on the left (little-endian), opposite the standard convention of writing numbers.


Of the 64 bit positions for each 64-bit constant, only 7 can ever be set, seen in the rough columns of 1s at bit positions 2^j-1 above.  Whether a position is set or not is taken from the output of the LFSR defined above (which is why we grouped the output in chunks of 7).  It is curious that Keccak uses such sparse binary round constants; the best explanation I can imagine is that it reduces the gate count in unrolled hardware implementations.  It's nice that Keccak is secure despite such weak round constants which barely modify values each round and differ so little between rounds.

The last round (of 64-bit Keccak, i.e., w=64) always uses the round constant with index 23 above.  If you wish to do Keccak with fewer than 24 rounds, then start somewhere in the middle, ending at round 23.  If you wish to do Keccak with more than 24 rounds, then start at a negative round index.  This is kind of bizarre, but I think the reason is something along the lines of being able to reuse cryptanalytic results from reduced-round variants.  Incidentally, negative round indices means that the rc(t) function must be able to handle negative t, so your (mod 255) operation must give a proper positive result for negative input.  Because 255 (the period of the LFSR) and 7 (the number of bits consumed per round constant) are relatively prime, the round constants cycle with a period of 255.  The period could have been less if the number of LFSR bits consumed per round constant shared factors with 255=3*5*17.  Here is the full list of round constants (in big-endian hexadecimal) for as many rounds of Keccak you care to do:

RC[-231] = 0x8000000080008082
RC[-230] = 0x800000008000800a
RC[-229] = 0x8000000000000003
RC[-228] = 0x8000000080000009
RC[-227] = 0x8000000000008082
RC[-226] = 0x0000000000008009
RC[-225] = 0x8000000000000080
RC[-224] = 0x0000000000008083
RC[-223] = 0x8000000000000081
RC[-222] = 0x0000000000000001
RC[-221] = 0x000000000000800b
RC[-220] = 0x8000000080008001
RC[-219] = 0x0000000000000080
RC[-218] = 0x8000000000008000
RC[-217] = 0x8000000080008001
RC[-216] = 0x0000000000000009
RC[-215] = 0x800000008000808b
RC[-214] = 0x0000000000000081
RC[-213] = 0x8000000000000082
RC[-212] = 0x000000008000008b
RC[-211] = 0x8000000080008009
RC[-210] = 0x8000000080000000
RC[-209] = 0x0000000080000080
RC[-208] = 0x0000000080008003
RC[-207] = 0x8000000080008082
RC[-206] = 0x8000000080008083
RC[-205] = 0x8000000080000088
RC[-204] = 0x0000000000008089
RC[-203] = 0x0000000000008009
RC[-202] = 0x8000000000000009
RC[-201] = 0x0000000080008008
RC[-200] = 0x0000000080008001
RC[-199] = 0x800000000000008a
RC[-198] = 0x800000000000000b
RC[-197] = 0x0000000000000089
RC[-196] = 0x0000000080000002
RC[-195] = 0x800000000000800b
RC[-194] = 0x000000008000800b
RC[-193] = 0x000000000000808b
RC[-192] = 0x0000000080000088
RC[-191] = 0x800000000000800a
RC[-190] = 0x0000000080000089
RC[-189] = 0x8000000000000001
RC[-188] = 0x8000000000008088
RC[-187] = 0x8000000000000081
RC[-186] = 0x0000000000000088
RC[-185] = 0x0000000080008080
RC[-184] = 0x0000000000000081
RC[-183] = 0x800000000000000b
RC[-182] = 0x0000000000000000
RC[-181] = 0x0000000000000089
RC[-180] = 0x000000008000008b
RC[-179] = 0x8000000080008080
RC[-178] = 0x800000000000008b
RC[-177] = 0x8000000000008000
RC[-176] = 0x8000000080008088
RC[-175] = 0x0000000080000082
RC[-174] = 0x000000000000000b
RC[-173] = 0x800000000000000a
RC[-172] = 0x0000000000008082
RC[-171] = 0x8000000000008003
RC[-170] = 0x800000000000808b
RC[-169] = 0x800000008000000b
RC[-168] = 0x800000008000008a
RC[-167] = 0x0000000080000081
RC[-166] = 0x0000000080000081
RC[-165] = 0x0000000080000008
RC[-164] = 0x0000000000000083
RC[-163] = 0x8000000080008003
RC[-162] = 0x0000000080008088
RC[-161] = 0x8000000080000088
RC[-160] = 0x0000000000008000
RC[-159] = 0x0000000080008082
RC[-158] = 0x0000000080008089
RC[-157] = 0x8000000080008083
RC[-156] = 0x8000000080000001
RC[-155] = 0x0000000080008002
RC[-154] = 0x8000000080000089
RC[-153] = 0x0000000000000082
RC[-152] = 0x8000000080000008
RC[-151] = 0x8000000000000089
RC[-150] = 0x8000000080000008
RC[-149] = 0x8000000000000000
RC[-148] = 0x8000000000000083
RC[-147] = 0x0000000080008080
RC[-146] = 0x0000000000000008
RC[-145] = 0x8000000080000080
RC[-144] = 0x8000000080008080
RC[-143] = 0x8000000000000002
RC[-142] = 0x800000008000808b
RC[-141] = 0x0000000000000008
RC[-140] = 0x8000000080000009
RC[-139] = 0x800000000000800b
RC[-138] = 0x0000000080008082
RC[-137] = 0x0000000080008000
RC[-136] = 0x8000000000008008
RC[-135] = 0x0000000000008081
RC[-134] = 0x8000000080008089
RC[-133] = 0x0000000080008089
RC[-132] = 0x800000008000800a
RC[-131] = 0x800000000000008a
RC[-130] = 0x8000000000000082
RC[-129] = 0x0000000080000002
RC[-128] = 0x8000000000008082
RC[-127] = 0x0000000000008080
RC[-126] = 0x800000008000000b
RC[-125] = 0x8000000080000003
RC[-124] = 0x000000000000000a
RC[-123] = 0x8000000000008001
RC[-122] = 0x8000000080000083
RC[-121] = 0x8000000000008083
RC[-120] = 0x000000000000008b
RC[-119] = 0x000000000000800a
RC[-118] = 0x8000000080000083
RC[-117] = 0x800000000000800a
RC[-116] = 0x0000000080000000
RC[-115] = 0x800000008000008a
RC[-114] = 0x0000000080000008
RC[-113] = 0x000000000000000a
RC[-112] = 0x8000000000008088
RC[-111] = 0x8000000000000008
RC[-110] = 0x0000000080000003
RC[-109] = 0x8000000000000000
RC[-108] = 0x800000000000000a
RC[-107] = 0x000000000000800b
RC[-106] = 0x8000000080008088
RC[-105] = 0x000000008000000b
RC[-104] = 0x0000000080000080
RC[-103] = 0x000000008000808a
RC[-102] = 0x8000000000008009
RC[-101] = 0x0000000000000003
RC[-100] = 0x0000000080000003
RC[-99] = 0x8000000000000089
RC[-98] = 0x8000000080000081
RC[-97] = 0x800000008000008b
RC[-96] = 0x0000000080008003
RC[-95] = 0x800000008000800b
RC[-94] = 0x8000000000008008
RC[-93] = 0x0000000000008008
RC[-92] = 0x8000000000008002
RC[-91] = 0x8000000000000009
RC[-90] = 0x0000000080008081
RC[-89] = 0x000000000000808a
RC[-88] = 0x000000008000800a
RC[-87] = 0x0000000000000080
RC[-86] = 0x8000000000008089
RC[-85] = 0x800000000000808a
RC[-84] = 0x8000000080008089
RC[-83] = 0x0000000080008000
RC[-82] = 0x8000000000008081
RC[-81] = 0x000000008000800a
RC[-80] = 0x0000000000000009
RC[-79] = 0x8000000080008002
RC[-78] = 0x000000008000000a
RC[-77] = 0x0000000080008002
RC[-76] = 0x8000000080000000
RC[-75] = 0x0000000080000009
RC[-74] = 0x0000000000008088
RC[-73] = 0x0000000000000002
RC[-72] = 0x0000000080008008
RC[-71] = 0x0000000080008088
RC[-70] = 0x8000000080000001
RC[-69] = 0x000000008000808b
RC[-68] = 0x8000000000000002
RC[-67] = 0x8000000080008002
RC[-66] = 0x0000000080000083
RC[-65] = 0x0000000000008089
RC[-64] = 0x0000000000008080
RC[-63] = 0x8000000080000082
RC[-62] = 0x8000000000000088
RC[-61] = 0x800000008000808a
RC[-60] = 0x000000000000808a
RC[-59] = 0x0000000080008083
RC[-58] = 0x000000008000000b
RC[-57] = 0x0000000080000009
RC[-56] = 0x0000000000008001
RC[-55] = 0x0000000080000089
RC[-54] = 0x8000000000000088
RC[-53] = 0x8000000080008003
RC[-52] = 0x0000000080008001
RC[-51] = 0x8000000000000003
RC[-50] = 0x8000000080000080
RC[-49] = 0x8000000080008009
RC[-48] = 0x8000000080000089
RC[-47] = 0x000000000000000b
RC[-46] = 0x8000000000000083
RC[-45] = 0x0000000080008009
RC[-44] = 0x0000000080000083
RC[-43] = 0x0000000000008000
RC[-42] = 0x000000008000800b
RC[-41] = 0x0000000000008002
RC[-40] = 0x0000000000000003
RC[-39] = 0x000000008000008a
RC[-38] = 0x8000000080000002
RC[-37] = 0x0000000000008001
RC[-36] = 0x0000000080000000
RC[-35] = 0x8000000080000003
RC[-34] = 0x0000000000000083
RC[-33] = 0x800000008000808a
RC[-32] = 0x0000000000008003
RC[-31] = 0x0000000000008008
RC[-30] = 0x800000000000808b
RC[-29] = 0x8000000080000082
RC[-28] = 0x8000000000000001
RC[-27] = 0x8000000000008001
RC[-26] = 0x800000008000000a
RC[-25] = 0x8000000080008008
RC[-24] = 0x800000008000800b
RC[-23] = 0x8000000000008081
RC[-22] = 0x0000000080008083
RC[-21] = 0x0000000080000082
RC[-20] = 0x0000000000000082
RC[-19] = 0x8000000080000081
RC[-18] = 0x8000000080000002
RC[-17] = 0x0000000000008088
RC[-16] = 0x000000000000008b
RC[-15] = 0x0000000000008083
RC[-14] = 0x8000000000000008
RC[-13] = 0x000000008000008a
RC[-12] = 0x800000008000008b
RC[-11] = 0x000000008000808a
RC[-10] = 0x8000000000008080
RC[-9] = 0x0000000080000088
RC[-8] = 0x8000000000008083
RC[-7] = 0x0000000000000002
RC[-6] = 0x0000000080008081
RC[-5] = 0x0000000000008003
RC[-4] = 0x0000000000008081
RC[-3] = 0x8000000080008000
RC[-2] = 0x0000000000008002
RC[-1] = 0x000000000000008a
RC[0] = 0x0000000000000001
RC[1] = 0x0000000000008082
RC[2] = 0x800000000000808a
RC[3] = 0x8000000080008000
RC[4] = 0x000000000000808b
RC[5] = 0x0000000080000001
RC[6] = 0x8000000080008081
RC[7] = 0x8000000000008009
RC[8] = 0x000000000000008a
RC[9] = 0x0000000000000088
RC[10] = 0x0000000080008009
RC[11] = 0x000000008000000a
RC[12] = 0x000000008000808b
RC[13] = 0x800000000000008b
RC[14] = 0x8000000000008089
RC[15] = 0x8000000000008003
RC[16] = 0x8000000000008002
RC[17] = 0x8000000000000080
RC[18] = 0x000000000000800a
RC[19] = 0x800000008000000a
RC[20] = 0x8000000080008081
RC[21] = 0x8000000000008080
RC[22] = 0x0000000080000001
RC[23] = 0x8000000080008008

The final 24 constants agree with those published at Team Keccak.  If you need more than 255 rounds, RC[-232] loops back to RC[23] and so forth.

Observations: In 24-round normal Keccak, rounds 5 and 22 use the same round constant, as do rounds 6 and 20.  Keccak with 25 rounds or more additionally sees the same round constant on rounds -1 and 8.  27 rounds or more sees duplication at rounds -3 and 3.  At 255 rounds (full period), there are 128 unique round constants, with every constant repeated twice except the zero constant which only occurs at round -182.

32-bit Keccak (w=32) uses the lower 32 bits of the round constants above.  7 bits of the LFSR are still consumed for each constant; 1/7 of the bits are thrown away.  There are by default 22 rounds total with last round having round index 21.  Duplicated pairs are rounds (6,20) and (11,19).  Doing more rounds causes more repeated round constants: doing 6 additional rounds (22 + 6 = 28 total) sees triplication of constants in rounds -6, 6, and 20.  16-bit Keccak has 20 rounds, duplication at (0,5), (4,12), (7,10), and (11,19) and first triplication with 6 extra rounds (-6,-4,6).  8-bit Keccak (18 rounds) sees repeated constants in rounds (0,5), (2,8), (4,12,13), and (7,10).

If we wish to extend Keccak to 128-bit lane width (w) or more, we would want to consume more than 7 LFSR bits per round, maybe also use a longer-period LFSR.  This should be safe, as these round constants are Nothing-Up-My-Sleeve numbers, so other numbers should also be safe to use.  A deeper Keccak will probably want other modifications also, for example the rho step-mapping function.  Its 25 triangular numbers, representing rotation amounts, grow only up to 300, but we would like larger rotations for better diffusion if the lane width is significantly longer than 300.

Here is an implementation in Haskell of the generation of these Keccak round constants.  We represented bit strings as lists of Bool.

Sunday, May 06, 2018

[ysmqgzjh] Chess ponds and columns

Consider a chess variant in which certain squares are designated not accessible: no piece may occupy them.  There are two possibilities: if a ranged piece (e.g., rook, bishop, queen) can fly over that square, then it is like a pond.  If the ranged piece is blocked, then it is like a rock column.

Pawns easily get blocked by these squares (of either type).

There is one more related possibility: a square may be occupied but a ranged piece may not fly through it; it must stop on the square.  This like a rough patch or a sticky spot.

Squares could be randomly set at the beginning of the game providing initial variation like Chess960, or they could change state during the game, perhaps something some pieces can do.

Saturday, May 05, 2018

[dqkfnndt] Amplitude modulated harmonics

The amplitude of the fundamental frequency oscillates with period 1.  (NB: We are describing oscillation of the envelope of the waveform, not the oscillation of the waveform itself.)  The first harmonic (i.e., frequency twice the fundamental) with period phi, the golden ratio.  The second harmonic at period phi^2, then phi^3.  Because no power of phi is a multiple of another, over time, you will hear all possible timbres (not including inharmonic partials).

[amlhovsv] Core power

The core of the sun has power density 276.5 W/m^3, which is surprisingly low (but explainable because of the weakness of the weak nuclear force).  The density at the core of the sun is 150e3 kg/m^3 (150 times denser than water).  Divide them to get that the specific power at the core is 1.84 mW/kg.  Inverse is 542 kg/W.

Describe the physical models by which the above input numbers were computed, because of course we cannot go and sample the center of the sun.

[dayxephk] 1/x samples infinity

Sample uniformly between 0 and 1, excluding zero but including 1.  (NB: this behavior regarding endpoints is the opposite of what most standard random number generators do, so do 1-x if necessary.)  Compute 1/x to non-uniformly sample between 1 and infinity.  Subtract 1 if desired to sample between 0 and infinity (because infinity minus 1 is still infinity). Floor to sample a random integer.

This is an approximation to the Zipf distribution with exponent 2.  Previously, on approximating the Zipf distribution with the more common exponent 1.  We can also consider exponents between 1 and 2 but things are probably not so elegant.

We could start with a different distribution between 0 and 1, perhaps heavily weighted toward zero to generate larger numbers more frequently: I think 1/(1-x)^a.  The transformation function could also be something like b^(1/x-1).

Tuesday, May 01, 2018

[ulhglysj] Harmonic subdivisions of a day

The largest bell rings once a day, perhaps at noon.  The second largest bell twice a day, every 12 hours.  The next 3 times a day, and so forth.

It's unfortunately quite loud at midnight -- all the even numbered bells (but surrounded by relative quietness?).

Maybe only the divisors of 24 or 24*60.  36 bells suffice for once a minute.  24 for once every 15 minutes (sigma(24*60/4,0) in pari/gp).  3 or 2 octaves of a 12-tone chromatic scale.

Some bells only ever sound as part of a chord with other bells, so skip the more frequent bell? 

All bells ring at noon.  When ringing at the same time, should they ring simultaneously as a chord or or slightly offset as an arpeggio?

[hevxgxxm] Circle blobs

Investigate the family of blobby shapes defined in polar coordinates:

r(theta) = a0 + a1*sin(theta+phi1) + a2*sin(2*theta+phi2) + a3*sin(3*theta+phi3) + ...

This is very related to Fourier series of course.  The a1 term merely translates the circle of radius a0 so could be skipped.  a0 is the DC offset.

The a2 term does not create an ellipse, though it would be cool if it did.

We probably want to avoid the sum going negative to keep things from becoming confusing.  Higher harmonics should have smaller coefficients.  Motivation is, in a shape the first thing you notice is the DC offset (the size), and on closer examination you notice it is not a perfect circle and notice the details of the higher harmonics.

They could also be animated: amplitude modulated as a function of time, or phase changes as a function of time.  The latter seems better.  Each term could have different frequency: probably higher terms have lower frequency to avoid it becoming frenetic.  We would like to explore all combinations of phase angles, so maybe throw in some factors of the golden ratio (a different phi than the phase angle phi).

In 3D, spherical harmonics.

Previously similar.

[ndgnutrt] Letters randomly sampled from different pages

On a screen, the first page of text is shown as if a random slideshow with relative frequency 1, the second page with relative frequence 1/2, and so forth: Zipf distribution.  Put the most important information on the first page.

Or, do the same thing but with individual letters, perhaps color coded to be able to identify what came from which page.  It needs to be a monospace font so that letters overlap exactly.  Vaguely similar to the falling letters animation of The Matrix.

Saturday, April 28, 2018

[ikaajwwn] Golden subdivisions of a day

A day divided by phi, phi^2, etc.  Not sure what higher powers of phi might be useful for.

Also consider dividing the sidereal rotation period, not the 24-hour solar day.

0 = 24h 0m 0.000s
1 = 14h 49m 58.137s
2 = 9h 10m 1.863s
3 = 5h 39m 56.273s
4 = 3h 30m 5.590s
5 = 2h 9m 50.683s
6 = 1h 20m 14.907s
7 = 0h 49m 35.776s
8 = 0h 30m 39.131s
9 = 0h 18m 56.645s
10 = 0h 11m 42.485s
11 = 0h 7m 14.160s
12 = 0h 4m 28.326s
13 = 0h 2m 45.834s
14 = 0h 1m 42.491s
15 = 0h 1m 3.343s
16 = 0h 0m 39.148s
17 = 0h 0m 24.195s
18 = 0h 0m 14.953s
19 = 0h 0m 9.242s
20 = 0h 0m 5.712s
21 = 0h 0m 3.530s
22 = 0h 0m 2.182s
23 = 0h 0m 1.348s
24 = 0h 0m 0.833s
25 = 0h 0m 0.515s
26 = 0h 0m 0.318s
27 = 0h 0m 0.197s
28 = 0h 0m 0.122s

24 = 1.200 Hz
25 = 1.942 Hz
26 = 3.142 Hz
27 = 5.083 Hz
28 = 8.225 Hz
29 = 13.308 Hz
30 = 21.534 Hz
31 = 34.842 Hz
32 = 56.376 Hz
33 = 91.218 Hz
34 = 147.593 Hz
35 = 238.811 Hz
36 = 386.404 Hz
37 = 625.214 Hz
38 = 1.012 kHz
39 = 1.637 kHz
40 = 2.648 kHz
41 = 4.285 kHz
42 = 6.934 kHz
43 = 11.219 kHz
44 = 18.153 kHz
45 = 29.372 kHz
46 = 47.525 kHz
47 = 76.896 kHz
48 = 124.421 kHz
49 = 201.317 kHz
50 = 325.738 kHz
51 = 527.055 kHz
52 = 852.793 kHz
53 = 1.380 MHz
54 = 2.233 MHz
55 = 3.612 MHz
56 = 5.845 MHz
57 = 9.458 MHz
58 = 15.303 MHz
59 = 24.760 MHz
60 = 40.063 MHz
61 = 64.823 MHz
62 = 104.887 MHz
63 = 169.710 MHz
64 = 274.597 MHz
65 = 444.307 MHz
66 = 718.903 MHz
67 = 1.163 GHz
68 = 1.882 GHz
69 = 3.045 GHz
70 = 4.927 GHz
71 = 7.973 GHz
72 = 12.900 GHz
73 = 20.873 GHz
74 = 33.773 GHz
75 = 54.646 GHz
76 = 88.419 GHz
77 = 143.065 GHz
78 = 231.485 GHz
79 = 374.550 GHz
80 = 606.035 GHz
81 = 980.585 GHz
82 = 1586.619 GHz
83 = 2567.204 GHz
84 = 4153.823 GHz
85 = 6721.028 GHz

[iueeifyd] Building a black hole the straightforward way

Currently popular is the idea of constructing an artificial black hole (to use as a compact power source) out of light: a kugelblitz.  However, is that route to black hole easier than building one out of regular matter?  In thermonuclear bombs we've gotten pretty good at compressing matter using radiation pressure (hohlraum), so just scale it up.

[lajyvhrh] Mass = time = temperature = power

There exists a black hole mass whose Hawking radiation is in equilibrium with the current cosmic background radiation.  What is that mass?

Friday, April 27, 2018

[poaebmuk] Sphere constant

Pi is a mathematical constant used in the formulae for many geometric objects, of which we provocatively claim the most relevant in our 3-dimensional world is the sphere, not the 2D circle.

Arrange the digits of pi on or in a sphere.

Tuesday, April 24, 2018

[kkdnzbbn] Experiments with 1/x and the natural logarithm

The integral of 1/x is log(x).  For u=x+delta, the area under the curve between 1/u and 1/(u+1) is exactly log(u)-log(u-1) and approximately 1/x for some delta.  Define f(delta,x)=log(x+delta)-log(x+delta-1).  We experiment with different values of the delta offset, seeking to approximate 1/x well.

The value delta=0.5 is optimal for large x in the following sense.  Define the error function Y(delta,x)=1/f(delta,x) - x.  Then (limit (x tends to infinity) of Y(0.5,x)) = 0.  However, approximations for small x are not so good: f(0.5,1) = 1.0986 = 1/0.9102.  f(0.5,2) = 1/1.9576.

The value delta1=1/(e-1) = 0.581976706869326424385 causes the approximation to be exact at (only) x=1: f(delta1,1)=1.  f(delta1,2)=1/2.0413.

For general delta, we claim without proof that (limit (x tends to infinity) of Y(delta,x)) = delta-0.5.  For the above value delta1, f(delta1,x) ~= 1/(x+0.081976706869326424385) for large x.

Motivation is to sample from the Zipf distribution without having to compute and store partial sums of the harmonic series.  Could also do a hybrid approach of computing and storing the probabilities of the more frequent items and using the above continuous approximation for the rest.

Monday, April 16, 2018

[ljdyledo] Sort of UTF-6

We present an encoding of Unicode code points to printable ASCII characters while keeping English text still vaguely readable.  It accomplishes a similar purpose as Quoted-Printable.  This design is modeled after UTF-8.  We use 6-bit bytes instead of UTF-8's 8-bit bytes.  We also do not encode the number of continuation bytes in the first byte; instead, the most significant bit (high bit) signifies whether a byte is followed by further continuation bytes.  The last byte of a sequence does not have its high bit set, signifying it is the last byte of a sequence representing one Unicode character.  The binary bits of the Unicode code point numbers of various magnitudes are encoded big-endian into the x's as follows:

  • 0xxxxx
  • 1xxxxx 0xxxxx
  • 1xxxxx 1xxxxx 0xxxxx
  • 1xxxxx 1xxxxx 1xxxxx 0xxxxx
  • ...

This encoding can encode values of arbitrary size, in contrast to the 36-bit limit of UTF-8 extended in the obvious way.  But this is a moot point (for now) as Unicode was originally limited to 31 bits, and later (including currently) limited further to 21 bits.

Here, in order, are the 64 printing characters used to encode a 6-bit byte.  It is modeled after ASCII, but some common punctuation namely ;,-.? has been moved so that it remains unchanged when encoded.  (The moved punctuation was moved only up or down a column of the 16-wide ASCII table, preserving low-order bits out of tradition).  The second row, beginning with @, are characters that will only be used in multibyte sequences.  The first row, beginning with space, represents characters which will be unchanged when encoded but can also occur as the last byte of a multibyte sequence.


The following is how Unicode code points 0 through 127 are encoded.  Here is a 16-wide ASCII table to see the corresponding original characters.


The fact that some multibyte sequences are terminated by space (e.g., code points 48 and 64, corresponding to the digit zero and the at-sign respectively) is a little unfortunate.

Here is some more text containing higher Unicode code points, followed by its vaguely readable encoding:

lowercase Capitalized camelCase UPPERCASE numbers 0123456789 common punctuation ;,-.? at-sign @ exclamation ! (parentheses) time 12:01 tilde ~ ‘single curly quotes’ “double curly quotes” yen ¥ euro € en–dash em—dash ellipsis … y-umlaut ÿ eng ŋ tent emoji ⛺ fire kanji 火 canoe emoji 🛶 newline

lowercase Acapitalized camelAcase AuApApAeArAcAaAsAe numbers C CaCbCcCdCeCfCgChCi common punctuation ;,-.? at-sign A  bobA httpCjC?C? exclamation Cq CxparenthesesCy time CaCbCjC Ca tilde C. H@xsingle curly quotesH@y H@,double curly quotesH@- yen Ee euro HEl enH@sdash emH@tdash ellipsis HAf y-umlaut G? eng Jk tent emoji IWz fire kanji \Ck canoe emoji C]Wv newlineBj

We implemented an encoder and decoder in Haskell (after first trying in Perl but finding it to be the wrong tool).  Some code excerpts:

We represented bytes as lists of Bool, sometimes little-endian sometimes big-endian depending on where we were in the conversion.  This is highly space-inefficient, but does allow some elegant code.  Given a list of big-endian bytes, splitting off the initial bytes that all have their high (first) bit set is elegantly span head.  This is used in decoding.

type Bstring=[Bool];
myspan :: [Bstring] -> ([Bstring],[Bstring]);
myspan = span head; -- takeWhile (\l -> head l == True)

Conversion to binary is an unfold.  Output is little-endian.

to_binary :: Integer -> [Bool];
to_binary = unfoldr (\n -> if n==0 then Nothing else Just (case divMod n 2 of {(q,r) -> (r==1,q)}));

Conversion from big-endian binary to an integer is a fold.

from_binary :: [Bool] -> Integer;
from_binary = foldl' (\accum b -> 2*accum+(if b then 1 else 0)) 0;

A few times we relied on the fact that mod x y with x negative and y positive yields a positive result.  This is in contrast to rem x y which would return a negative result.

Wednesday, April 04, 2018

[dahjjtaq] Fingerprint and PIN

Are there any phones which can be set to requiring both scanning a fingerprint and typing a PIN or password in order to unlock, for increased security?

We want "and" not "or" as most phones currently do.

[xfkccubv] Decrypt incorrectly to comprehensible text

Use a very good language model (e.g., LSTM) when encoding and encrypting text so that decrypting with the wrong key will result not in nonsense but normal-seeming text.  One could give a false key under duress.

Bit of a problem that it needs to decrypt to text that it is plausible someone would want to encrypt; there isn't much of a language model for that.

Could also do for pictures: there is a good model, namely porn, for pictures people would want to encrypt.  Then, encrypt text as a picture of text.

Another scenario is a master key to a password manager.  Each encrypted password should have a "language model" associated with it (used or valid password characters, or a more sophisticated password generating scheme like diceware), then an incorrect master password will generate incorrect passwords consistent with its language model or scheme.

[njogcgwc] In praise of calculating pi

Calculating pi to a record number digits stress-tests CPU, memory, and disk: there must not be even a 1-bit error in (typically) months of calculation.

Better -- a less complicated calculation which accomplishes the same tasks -- would be calculating sqrt(2)/2 in binary.  It can more easily be checked afterwards: just square it or compute 0.5/x.  But does calculating pi (using a Ramanujan-style formula with binary splitting as recent PC-based (not supercomputer) records have) test things that sqrt(2) (presumably calculated using Newton's method, an algorithm more similar to Brent-Salamin, not used in recent record-setting pi calculations) would not?

We specify sqrt(2)/2 and not sqrt(2) to eliminate ambiguity about whether calculating N bits includes the bits to the left of the radix point for numbers greater than 1.  There is something elegant about the square root of X in base X: dividing by X is simply a right shift.  However, one could do radix conversion to base 10 at the end.

In contrast to pi, sqrt(2)/2 has a nice feature that subsequent calculations to more bits can start from a previously published result then do more Newton iterations.  Slightly better would be if the fraction, before the final division, were published.

Parallel over many computers would also stress-test network, though it might be tricky to avoid it becoming a bottleneck.  Maybe file storage with disk arrays interconnected by network.

Are there better ways to test these things?  Probably something involving cryptographic hashes like Argon2, though it's not so glamorous.  Also cache-oblivious matrix transpose.

Saturday, March 31, 2018

[myoypbbj] From hierarchical to a simple list of records

Given hierarchical data, e.g., html: <lorem>ipsum <dolor>sit</dolor> amet <a href="consectetur">adipiscing</a> elit </lorem>.  Expand it to a collection of records, for ease of processing with a record-oriented tool.

lorem _content ipsum <dolor>sit</dolor> amet <a href="consectetur">adipiscing</a> elit
lorem _contentdolor _content sit
lorem _contenta href consectetur
lorem _contenta _content adipiscing

If the records are printed 1 per line, then newlines in the content will need to be escaped.  Record separators, e.g., tab, in content will need to be escaped.

Other hierarchical data formats, e.g., JSON, probably don't need to do the _content pseudo tag.

Content could be an array, avoiding the repetition of content and tags broken down.

[caqwyduy] Belt and caps

A cube can be considered as having square two polar caps and a belt of 4 squares around its equator.  The belt can be conveniently unfolded, in the style of a polyhedral net, into a strip, which is nice for a map projection.  Also chess on a cube.

Similarly, a regular octahedron "on its side" can be seen as two triangular caps and a belt of six triangles in a strip.  In the tetrahedron, the caps are line segments and a belt of 4 triangles.  Probably not so good for a map projection, though I haven't seen it.  The equator should go through the middle of the belt.

The regular dodecahedron has two pentagonal caps and two rows of pentagons as its belt.  The belt no longer unfolds nicely into a contiguous strip.  Choose the unfolding which keeps the equator continuous.

Icosahedron: two caps of 4 triangles each, a center one and 3 neighbors.  The belt is a single row of triangles that weaves up and down between the caps.

This net of the truncated icosahedron (soccer ball) strongly suggests a belt and 2 pentagonal caps.

We can also consider points as caps, then all the faces as rows of belts.

[xjommsdj] Polyhedral map projections

Project the globe onto a cube then print the 6 faces onto 6 pages.  People understand square-shaped maps.  There are several ways to project 1/6 of a sphere onto each square face.

Of course, the four squares around the equator can be joined and printed onto a (long) flat page.

Each square could cover slightly more than 1/6 of a sphere, allowing overlap with neighboring squares for convenience.

Projection onto a cube is equivalent to views from the 6 vertices of the regular octahedron.  We could view from more than 6 points: what are some nice symmetric collections of points on a sphere?  Tammes problem.  We prefer symmetry so readers can understand how different pages relate to each other (especially in distance).  12 pages seems doable; maybe 20 corresponding to the vertices of the regular dodecahedron? The region covered will no longer be naturally square; use circles or the shape of the polyhedral face.  Azimuthal equidistant projection is nice for circles.

[hwvlhzae] Two patch failure possibilities

  1. Apply patch A
  2. Apply patch B
  3. Remove patch A

Patch A might have a conflict when trying to remove.  Or, it might seem to be cleanly removed but actually induce a hidden problem.

Software installation and uninstallation.

[pbldsmje] Evil next week

Look upon the face of true evil, perhaps the latest mass murderer or serial killer paraded in the news.  That could realistically be you next week: the Stanford Prison Experiment demonstrated that anyone can be turned -- in 6 days or less -- to commit atrocities.

If that face of true evil could very easily be yourself, then why are we contemptuous of Them?  There's something sociological going on.

Friday, March 30, 2018

[zognwxxq] Transferring files via USB cable on Android

Nexus 5x, Android 8.1.0, Ubuntu 16.04

Need USB-C to USB-A cable.

Enable Developer Mode.

Settings -> Developer Options -> Select USB Configuration -> MTP

It will automount at /run/user/NNNNN/gvfs .

It is good from a security standpoint that cable access is disabled when the phone is locked.

[nteqtrws] ifupdown in the NetworkManager world

Notes on toggling wifi:

nmcli help
nmcli connection help
nmcli connection
nmcli connection down (ap-name)
nmcli connection up (ap-name)

Does not require sudo.  Does not require retyping the wifi password.

Thursday, March 29, 2018

[teictrfe] VR on an office chair

Consider a virtual reality system in which your swivel chair simulates a vehicle, the direction your vehicle is pointing.  This is independent of which way your head is pointing.  The view you see in VR is the sum of orientations of your vehicle and your head.

Rotations around the vertical axis (yaw) of your vehicle are done by physically turning your chair.  This will require somehow tracking or sensing the rotation angle of the chair.  Other orientation changes (pitch, roll) of your vehicle are done with a hand controller, as are translation movements.

If the game has a horizon or a zenith-nadir axis, it probably makes sense to have those rotations always be around that absolute axis rather than the vertical axis relative the user's current orientation.  But this might be confusing if the user is upside down.  Gimbal lock might occur.

If you push the button to go "forward", you virtually go in the direction your chair (your vehicle) is facing.  You can look sideways while moving forward.

[aiwebpwx] Sexual fetish sim game

You play a god overseeing a world of simulated people as in The Sims. Your goal as a benevolent god is to make your sims happy.  Your sims have sexual fetishes which you need to predict or discover, then you need to manipulate the world so that your sims get them so they can achieve happiness.

Inspired by, the mechanisms which cause which people to develop which fetishes are not understood in the real world.

[nwtkgnqj] Rounding off a corner

Consider rounding off the corners of a parallelogram.  Easiest is to fit circles into the corners.  But another way is to round off the corners of a square or rectangle using circles then do an affine transformation to a parallelogram.  Then the fillet will not be a circular arc.

[nfeqogok] Intimidating refs

A coach or player gets into an argument with a referee or umpire.  Does it work?  That is, does it change how the referee referees for the rest of the game?  This can be measured.

The effect of players intimidating each other through fights and arguments can also be measured.

If it does work, to what extent should it be permitted?

Wednesday, March 28, 2018

[iwgjdcyx] Touch the high bar

The traditional high jump (kind of) measures how high you can elevate the lowest part of your body.  A different competition could measure how high you can elevate the highest part of your body, measuring the tip of your hand in a jump.  This is more realistic as a task people often do.  Use technology to measure the height, maybe a grid of lasers.

Of course, tall people will have a huge advantage, unlike traditional high jump.

[udoetndm] To crush then Schadenfreude

Step 1, to crush your enemies, is best in life only insofar as it consequently provides you the only true joy, Schadenfreude: to see them driven before you, to hear the lamentations of their women.

[ndcjjiev] Sphere world

Consider a virtual world built not out of cubes as in Minecraft but spheres arranged in a grid.  With an ambient-lighting-only lighting model, spheres are even simpler than cubes to render: just circles. However, one cannot render an entire flat face all at once as one can with a wall of cubes.

One can see through gaps between spheres, perhaps a nice feature for gameplay but a headache for computer graphics as testing occlusion becomes difficult.

Which grid of spheres? The one aligned with the centers of cubes is the most straightforward coming from Minecraft, but it is not a close packing.  The hexagonal close packing has infinitely deep holes in the gaps, but the face-centered cubic (fcc) packing does not (I think). Does fcc have lines through the packing which do not pass into the interior of any sphere?

[xyecmjsr] Rendering simplified Minecraft

A simplified world of cubes could be very simple to render: blocks are solid color only; lighting is ambient light only. How quickly can a large number of such blocks be rendered?  (This might be too simple; one will not be able to see the edges of cubes.  Maybe we want textures, or at least different colors for different cube faces.  Adding diffuse lighting would also not be difficult: there are only 6 normal vectors.)

As Minecraft demonstrated, sophisticated modeling and photorealistic lighting are not necessary for an enjoyable game. However, the ability to render large scenes is desirable, so keep things simple for performance.

[pgjogxxj] Warn using a default value

One additonal possibility wanted (beyond those previously mentioned): a function provides a default value for an argument, but the compiler emits a warning if the default value is used.

[vectvwqp] Animated vector graphics

Vector graphics can be rendered at any resolution. Extend the idea to animated vector graphics which can be animated at any time resolution: a function from a real-valued time variable to a vector graphics image.

We can also extend to 3D (and 3D + time); this is mostly already done: probably every 3D object representation except voxels.

Saturday, March 24, 2018

[zencjwey] Desktop UI keeps changing

It's unfortunate that despite the desktop UI (GUI) having being around for 40 years (Xerox Alto), designers still feel compelled to radically change things often, confusing people who learned the previous version, forcing them to rather pointlessly learn the new way of doing something.

We don't get the feeling that desktop interfaces are converging to an optimal design.

When in doubt, keep it looking and behaving like the old version.  New stuff supplements old, not replaces.  Keep the old way working even if there's a new way.  At least, where the old way was, leave instructions for the new way.

What are the forces for silly change?  Egos of designers, look and feel copyrights, patents, and trade dress, incentives to decrease functionality.

[efzxvlay] Optimal barriers to voting

Assume the objective function for a democracy includes preventing the majority from tyrannizing the minority.  Barriers to voting help accomplish this: a minority highly motivated not to be tyrannized will overcome the barriers while a majority only slightly in favor of tyrannizing will tend to be stopped by the barriers.  This magnifies the political power of the highly motivated, which probably helps things like preventing famine (Amartya Sen).

What is the optimal amount of barriers to political participation to maximize the (still unspecified) objective function of a democracy?  Barriers to participation are enacted and dismantled by the democratic political process: does a democracy naturally converge to the optimal amount of barriers?

Barriers to voting probably also decrease the power of demagogues, something democracies probably need to do some -- but not too much: another optimization problem.

[yrbtlvdw] Learn enough to translate

Learn a language just well enough to be able to use translation tools.  This probably means learning the alphabet (or common radicals for Chinese and Japanese), maybe phonemes for speech-input translation tools.

[gxzxttrh] Velocity sensitive game controller

We don't yet have game controllers which are sensitive to how hard or fast you push a button.  It seems very doable, and good for making games around that mechanic.

Inspired of course by the piano, and the possibility of making a musical instrument of that form.  In the meantime, consider using a velocity-sensitive electronic piano keyboard as a game interface.

Thursday, March 22, 2018

[ezjqmcuc] Locality because simulation

Our universe (mostly) obeys locality: information and influence do not travel faster than the speed of light.  Speculate that this is because we live in a simulation: simulation is easier if there is locality.  Can special and general relativity be seen as "ugly hacks" by our universe's engineers, forcing locality?

The famous violation of locality, quantum entanglement, mostly obeys locality: where the universe is dense, a particle/wave does not travel very far before it interacts with something else, forcing the wavefunction to collapse.  Where the universe is sparse, the simulators can do some sort of sparse computation, like sparse matrices.

[wercuqeo] Soldier Field in the future

"17776: What football will look like in the future" missed an opportunity to set game 27 in renovated Soldier Field, Chicago: "It's hideous".

[ahpsjsbl] Different sized air hockey

Experiment with air hockey on different sized tables and different goal sizes.  An arcade could offer different sizes.

[aobmrmdw] Outsourcing AFS

The Andrew File System seems like a service that could be easily provided by a 3rd party vendor.  Use large AFS caches to disguise high latency if the vendor is far away.

[magxbcla] Artistic football

Radically modify football by eliminating defense.  Points are awarded not just by moving the ball downfield (which is trivial in the absence of defense) but also doing it with style.

Number and rapidity of laterals, number of spins by a ball carrier, no-look maneuvers, leaping maneuvers, choreography of players in pretty patterns.

Collision injuries will hopefully decrease.

[zxevkvev] Walking houseplants

I have yet to see anyone take their house plant out on a walk.  It doesn't seem too difficult: load it onto a wagon.  Maybe even practical: get some sun.

Inspired by cats on leashes.

[tqodhrnz] Command line with text formatting

For an enhanced terminal application, let output have text formatting, with pipe utilities to interpret and render markup like HTML or LaTeX (just a subset of such markup).

Previously, images.

[dhipnjdq] Multi word identifiers in Lisp

We consider a programming language that allows identifiers with spaces in them, eliminating the need for camelCase, underscores, or dashes in identifiers.  We consider building on Lisp syntax, which is the most challenging because of Lisp's limited syntactical elements.

Easiest is for multi-word identifiers to have a parenthesized special form, preceded by a reserved word signifying a multi-word identifier:(sine x) ((mwi inverse sine) x)

Making mwi a reserved word does subtract that word from the user's available namespace; however, things like (mwi my mwi) are available.  Alternative words: "id", some symbol, and... "multiWordIdentifier".  The irony is that "multi-word identifier" is itself a multi-word identifier, but we can't use it to signify itself, or else we fall into a recursive rabbit hole like (((mwi multi word identifier) inverse sine) x).

Intriguingly, multi-word identifiers in Lisp allow parentheses within identifiers: ((mwi sine (implemented by Bob)) x), ((mwi (multi word) identifier (avoiding a dash)) x)

Another way to do it is to let multi-word identifiers be simply parenthesized: (inverse sine).  This interferes with function call syntax, so we modify function call syntax with a reserved word "do": (do sine x) (do (inverse sine) x).

Using up "do" as a reserved word prevents any multi-word identifier from starting with the word "do".  We could use some other word or symbol, perhaps period: (. (inverse sine) x).  This steals syntax from Lisp dotted pairs, so use another symbol for dotted pairs, assuming one wants to keep that feature.

Period to signify function invocation could be made more unobtrusive by making it postfix, radically departing from Lisp's normal prefix convention: (sine x .) ((inverse sine) x .)

Explicitly invoking functions is reminiscent of Haskell's $ operator.  It also suggests providing many different options on how to invoke a function, e.g., lazy evaluation, concurrency.

[bnekxptx] Tired but happy

One can be in a state of being tired but happy.  Tiredness is associated with low self-qi (often in the combination tired and irritable), but happiness is associated with with high.  Which is actually going on, assuming self-qi can be objectively measured in responses to and perception of unpleasant or stressful stimuli while in that state?

Some people like to cuddle in that state.  Cuddling is an activity associated with high self-qi; with low self-qi, you don't want to be around people, nor can you handle things going wrong.

Wednesday, March 21, 2018

[jpanfkuk] Summertime suppertime

Mash up "Summer time, and the living is easy" with "Supper time" from You're a Good Man, Charlie Brown.

[qdhplkfr] Adjusting VR field of view

Virtual reality can provide a viewer with a wider field of view then they would naturally see.  Perhaps useful for first-person games, decreasing the chances of someone sneaking up behind you.

One can compress the field of view linearly, or nonlinearly with normal angles near the center of vision and distortion near the edges.

[oynrnmoz] VR binocular vision

In virtual reality, provide a control to adjust binocular separation, the amount of parallax between the two eyes.  Make it useful for a game somehow?  Previously

[bgrwfcni] Draw the minimum graph

Given some points in the plane, draw the minimum Traveling Salesman's Path.  Or, Euclidean Steiner Tree.  These seem pretty easy to make into competitive games: whoever has the current best solution earns points based on time until someone else finds a better one.

For Euclidean Steiner, the player draws a topology and the computer automatically does local minimization to compute the total edge length.  Perhaps no one earns points until the approximate tree based on locally optimizing the minimum spanning tree is beaten.

In 3D with VR.

[qiiemukv] More battles of wits

The location of the Battle of the Wits in The Princess Bride seems to be accessible in a national park in England.  What are its exact coordinates?  "Lathkill Dale where it meets Cales Dale in Peak District National Park, England" according to Wikipedia.  One could film other battles of wits there, maybe a chess game.

Monday, March 19, 2018

[dwpotjwt] Spirals on spirals

Draw a line in 3D space.  Draw a helix around that line.  Draw another thinner helix around the first helix.  Repeat.  Probably related to Fourier transform.

Wrap a logarithmic spiral around a cone.  Repeat the previous construction, with the helices getting thinner as it approaches the apex of the cone.  Arc length might remain finite.

[ovnejymj] Fairy chess pieces in foreign languages

Using the name "wazir" as a fairy chess piece will cause confusion where that word is already used for what English-speakers call the Queen piece (e.g., Hungary and Azerbaijan are countries where chess is very popular.  Hindi.).  Similarly, "ferz" is the queen in Russian (and others).  Arabic uses both for the queen.

Similarly, "alfil" as a fairy chess piece will cause confusion where that word is already used for bishop (Spanish, and others), and relatedly "fil" (Azerbaijan, Persian, and others).

Invent systematic names for a nice subset of fairy chess pieces that does not run into problems with translation.

[efpkpefb] TINA

stands for "TINA Is Not an Acronym" (or Abbreviation).  Or any ?INA, ?NA, ?IA.  Inspired by GNU.

Renaming the CIA to "CIA Is an Acronym" (and that's all you Need To Know) seems like something an intelligence agency might do.  Also DIA.

[xymeylpw] Base 29

Slightly modify the previous system of encoding arbitrary Unicode with 30 characters by making open parenthesis the escape character.  We no longer get short escape sequences, nor can parentheses be used directly in text, but escape sequences can easily be ended with close parenthesis.

Is the scope of an escape sequence limited to what's within the parentheses?  Should capitalization be (caps a) or (caps)a?  (allcaps ibm) or (begin allcaps)ibm(end allcaps)?

This resembles HTML with parentheses instead of angle brackets.

[ynrhmpbn] Integer and real zooms

When magnifying a raster image, sometimes you want integer zooms, turning pixels into square blocks of pixels.  Other times you want smooth interpolation, e.g., bilinear or bicubic.

[mjdtvttx] Flipping function composition

Here is how to refer to the function composition operator in Haskell when it has a qualified prefix: "Prelude..".  It certainly looks very weird.  Here it is in the context of creating an operator which puts its arguments in an order which some might consider more natural.

import Prelude hiding ((.));
import qualified Prelude;
(.) :: (a -> b) -> (b -> c) -> a -> c;
(.) = flip (Prelude..);

But consider just using the builtin operator Control.Category.>>> instead of redefining "." in this way.

Sunday, March 18, 2018

[czqkaghm] Some integers

Is your number theory conjecture true of all nonnegative integers?  Some numbers to test looking for counterexamples:

0, 1, 2, 3 (first odd prime), 4 (first square larger than 1), 6 (first product of two distinct primes), 8 (first cube larger than 1), 9 (first square of an odd prime), 15 (first product of distinct odd primes), 27 (first cube of an odd prime), 30 (first product of 3 primes), 105 (first product of 3 odd primes).


And of course, try some negative numbers if you suspect it true for all integers.

[zmlnouxm] Freenet for point to point communication

Create a system by which two parties can communicate but an eavesdropper has difficulty even telling that a message is being sent.

One solution is to piggyback on a system which is constantly sending messages, and messages are routed through multiple hops.  Can Freenet work for this purpose?

Global traffic analysis, looking at message sizes and timing, might be enough for an eavesdropper to connect the two parties.  Maybe nodes can collect messages over a time period and send them to another node as a bundle.  This disguises message sizes and introduces more delays making timing analysis difficult.

Inspired by David Petraeus and Paula Broadwell communicating through Gmail drafts of a shared account.  What if it was far more difficult to tell that either of them was connecting to a common service?

[xhazmizv] Genocide and economic well-being

Hypothesize there is negative correlation between a country's economic well-being and its predilection to commit genocide.  The hypothesized mechanism is they are looking for a scapegoat to blame for their economic troubles.

Is this true?  I suspect there is lots of data to test this hypothesis.  Are there exceptions (low economic well-being but no genocide, or high economic well-being with genocide)?  How can one explain the exceptions (if there are any)?

To what extent can the economic troubles of Germany after World War I be attributed to actions taken by the WWI victor countries seeking spoils of war, e.g., reparations?  Assuming true the causality from economic downturn to genocide, this becomes an intensely political question: who is to blame for the Holocaust?

[skbsmufv] Reverse Rubik's cube competition

The solver is shown a pattern (most likely a scrambled state), given a solved cube, and asked to transform the solved cube to the given pattern as fast as possible.

Thursday, March 15, 2018

[uubpwgfn] Paradox of promiscuity

Having sex, aiming for enjoyable sex, is inherently a risky activity: you have to put yourself in a physically or emotionally vulnerable state to maximize enjoyment.  However, things could go wrong in such a state: you could get hurt.  To handle and recover from things going wrong requires a positive attitude, mental fortitude: high self-qi.

Therefore, one would expect a correlation between people who have sex with many partners and high self-qi.  Therefore, we would expect that people believed to have had sex with many partners would be prized for courtship: prefer partners who signal (as in game theory imperfect information) high self-qi.

This seems not to be occurring: In women, promiscuity is very frequently looked down upon ("slut"), and in men, although it carries value ("stud"), the meaning of that value does not seem to be because it directly signals high self-qi.

Possible explanations resolving this paradox:

This model of self-qi is entirely wrong.

The reason some people have had many sexual partners is because they can't retain them, losing them because of their own low self-qi or some other flaw like lack of commitment or loyalty.

Self-qi is a currency that can be used to advance yourself in many ways.  Those who choose to spend it on having sex are doing so because of lack of other opportunities, signaling low social status.  Future post: on the history social dancing.

People are not being rational in how much sex they have.  This seems incorrect: people make less mistakes the more chances they have to try and learn from their mistakes, so a promiscuous person for whom promiscuity is rationally bad decision will learn not to have sex so often.  Similarly, those for whom promiscuity is rationally a good decision will shift towards it, though this is contingent on other people wanting to have sex with you.

Something involving sexual economics.

[obxqhvtm] Contagious handrails

Should you hold the handrails of public stairs or an escalator?  On one hand (no pun intended), you are touching the thing everyone before you touched, so exposing yourself to everything contagious those people had.  On the other hand, stairs are some of the most vicious killers out there due to slips and falls.  Even a light maiming by stairs can leave you injured for life.

The problem is somewhat game theoretic. The degree to which handrails are coated with contagious disease depends on how much everyone else touches it.  The degree to which everyone else touches it depends on what they believe to be the contagiousness of the handrail.

[ekeyyuib] Many vulnerable Android devices?

How many active Android devices are out there, no longer being patched for security vulnerabilities by their manufacturers?  It is of course a shame that otherwise perfectly fine hardware reaches this state: DRM at work, as well as not-too-large an ecosystem of alternative well-maintained distros one can install on one's phone.

Wednesday, March 14, 2018

[kfernrxl] Politics and pro wrestling

Tell a story juxtaposing the behind-the-scenes of both politics and pro wrestling, each side scripting a story for the people to consume, full of invented and hyped-up conflicts.

Sunday, March 04, 2018

[omvgtkqp] Dodecahedral edge cover

Can one partition the faces of an icosahedron into 10 non-overlapping pairs of adjacent faces?  Some simple investigation suggests yes.  If so, one can set up a grid on each nonplanar rhombus by connecting opposite edges.  If distortion is OK (e.g., in a game), this can be a map with 10 square shaped regions connected to each other.

Are there any nicely symmetric face pairings?  Zonohedra, polyhedra with all faces parallelograms (the "more restrictive definition" according to George Hart) exist, including the nicely symmetric rhombic dodecahedron and rhombic triacontahedron.

Equivalently, this partitions the surface of a sphere into 10 congruent rhombus shaped patches.  Equivalently, it is an edge cover of the regular dodecahedral graph.

What happens when this is done on a octahedron?  There seem to be two ways of doing it: 4 wedges from pole to pole, or 2 sideways with respect to the other 2 reminiscent of a sphericon.

[hurozhls] Large chess is like go

Chess on large boards and especially in higher dimensions might feel more like go 囲碁.  There are many battles going on in different parts of the board which only weakly interact because it takes many moves for a piece involved in one battle to move to influence another battle.  Perhaps enhance this characteristic by limiting long-range movement to only the movement of the small rook, parallel to orthogonal axes.  Another possible enhancement: forbid long-range captures.

Change the scoring to be more like go.  There is no king, no checkmate.  The game ends with 3 fold repetition or consecutive passes.

For a static final position (consecutive passes) score it by something like territory: maybe the number of squares your pieces can reach before any opponent's piece.  If the final position is a loop (repetition) take the average over the loop.  Scoring is complicated and best done by computer.

Perhaps the initial position has every square occupied, so there is something to play for, not immediately passing.

[bljdmymf] Shortest paths for higher dimensional chess pieces

Given a higher dimensional rook or bishop as previously described, compute a path which reaches a given destination in the smallest number of moves.

In 2D on an empty board, a rook or bishop takes at most 2 moves to reach any given (accessible) square, and it is not difficult to describe the positions in which they require only 1.

In N dimensions, I suspect at most N moves are necessary (which is a lot).  When can we get there in less, and how?

The movement of both pieces can be described as a integer scalar multiple of a vector whose components are all -1, 0, or 1.  For a bishop, the number of nonzero components is even; for a rook, odd.  Without loss of generality, assume the piece is at the origin.  Find moves which sum to the coordinates of the destination.  This seems reminiscent of bin-packing.

One heuristic is, for all possible moves from the current location, choose the one that minimizes the straight-line (Euclidean) distance to the destination: the distance from a point to a line.  Repeat for the next move.

Other open problems: computational complexity; the tricky knight; what if there are obstacles?

[tjwlghtv] Limited higher dimensional chess pieces

A family of additional pieces for higher dimensional chess:

The Small rook, wazir, and dabbaba move only parallel to orthogonal axes.  2*D possible directions.  This is the most obvious generalization of the rook to higher dimensions, but originally rejected because of how relatively weak it becomes in higher dimensions.

The Small bishop, ferz, and alfil move only in the directions of longest-length space diagonal.  In odd dimensions, the pieces are not colorbound.  2^D possible directions.

The Small knight jumps to a square reachable by one Small wazir move then one Small ferz move in the outward direction.

Of course, these abilities can be combined to form compounds like a queen.

Compared to the Great versions of the pieces previously described, these pieces are relatively much weaker.  The Great rook and bishop both move in approximately 3^D/2 possible directions.  However, the weakness of the Small versions might enhance a game in which pieces rarely interact over large distances.

Saturday, March 03, 2018

[eltiajwk] Short Diceware

We consider generating passwords using dice, inspired by Diceware.  However, unlike Diceware, we generate short, non-memorable passwords, intended for use with a password manager.

A-Z a-z 0-9 and two punctuation give 64 characters, suitable for 2 throws of a d8 (octahedron) die, looking up the letter in a compact table, in contrast to Diceware's very long lists.  The choice of the 2 punctuation characters depends on what punctuation is permitted for that site.

A d20 labeled with the 20 most common initial letters.  d24 and d30 exist as Catalan solids.  For d30, the 4 extra faces could be reroll, common letters (maybe vowels?), numbers, or punctuation.  Previously, on how to turn a random string into a sentence.

[tvuxbiuq] Password generation with a deck of cards

Easiest is to mark up the fronts of deck of 52 cards with lowercase a-z and uppercase A-Z.  (It's convenient how the numbers work out.)  Shuffle and get some random letters.  Drawing with replacement (shuffling after each draw) has slightly more entropy, but requires more effort.  Use the number cards (rejecting face cards) if you need to add some digits to satisfy password character class requirements.

We need a way of writing individual letters to distinguish uppercase from lowercase: c o p s u v w x z.  Maybe tilde or macron for lowercase, as these conveniently do not have ascenders.  Or cursive.

Slightly more sophisticated is to add 10 number cards from a separate deck, bringing the total up to 62: letters and digits. Add jokers or more face cards for punctuation.

Sites often disagree on what punctuation is permitted/required.  Is there a set of 2 (for jokers) or 3 (for face cards) which are usually permitted?

These would not be memorable passwords, so use a password manager.

[ebxhxgtj] Despacito magnets

The song Despacito could be interpreted as about science, the attraction of metal to a magnet.  Create a music video to the song illustrating magnets in action.

[ttjsbzma] Avoiding the birthday paradox

Each person draws with replacement from an urn containing N balls.  For a given population size, how large should N be so that the probability of collision is smaller than some given small probability?  Of course, larger than Population^2 because probabilities are around 50% there.

If we want collisions to "never" happen, what should that small probability be?  2^-128? 2^-256?  Randomly chosen 128-bit UUIDs only offer 2^64 collision resistance, probably OK for each human on earth choosing just one, but not enough for (say) tagging rapid transactions.

Inspiration was, how does a galactic civilization with a population on the order of 2^114 choose unique identifiers, e.g., the future equivalent of Social Security Numbers, for each person in a distributed way (not requiring central coordination because communication might be expensive)?  Or, how should it assign IP addresses to its galactic network of computers (though that might be more difficult, also requiring solving routing)?

[iaqaplhi] Star Trek: K3

Tell stories of a Star Trek-like universe (people generally get along, not war all the time) taking place in a galaxy colonized to Kardashev level 3.  Most stars have Dyson spheres (swarms) around them.  We probably need FTL travel and communication.

Assuming a person requires an average of 4 kW of power (including energy cost of agriculture to grow their food), a galaxy's power output can support a population of 10^34.

If this were instead a Star Wars-like universe with such a population, a quadrillion deaths would not be a big deal, proportionally less (much much less) than 1 person dying on our planet of 7 billion.

[dpxfesvt] Inventing evolving languages

Invent not just one fictional language but multiple versions of it corresponding to snapshots over time for a story that takes place over a very long time.  How do languages realistically evolve?  Inspired by Tolkein.

[iiycledq] Fastest cryptographic RNG

How quickly can cryptographically secure pseudorandom numbers be generated?  Probably something parallel that runs on GPU.

Assume that we are consuming such a large quantity of random numbers that statistical irregularities that show up after 2^64 samples will become visible.  This means we cannot just use AES in counter mode to generate a random stream.

This seems useful only as a curiosity: what could need so much cryptographic randomness so quickly?  Monte Carlo simulations do not require cryptographic security.  What could even consume numbers that quickly?

Maybe high-bandwidth encrypted communications of data at rest.  Other than data at rest, it's hard to imagine data being produced so quickly as to require an extremely fast cPRNG to encrypt it.  But even data at rest is limited by disk bandwidth.

[rgifeuwg] Human power

Another way of putting amounts of power or energy into human-comprehensible terms is to compare it with a human on an exercise bike.  Previously.

[dlowwfka] Car average power

A car with fuel efficiency of 20 miles per gallon traveling 20 miles per hour on average conveniently consumes 1 gallon of gasoline per hour (similarly 30 and 30, etc.).  This translates to 36000 watts.  Less if your car has better gas mileage.

[qdkedsco] Thwarting the evil maid

Preventing physical attacks against unattended computers carrying valuable data is simply the problem of physical security, e.g., safes and locks, which has been studied for a very long time, though this is a new form factor.

Desired features: A laptop which can be locked closed with a lock (maybe padlock) of the user's choosing so that the user can balance security versus convenience.  Laptop cannot be disassembled while locked.  Ports cannot be accessed while locked.

Some users may want tamper-proof physical security; others may just want tamper-evident physical security.  Tamper-evident can interface with the computer to record and notify attempts at tampering.

[smofltff] Connect the dots

In a workbook, provide many pages offer practicing drawing the same image many times with numbered dot-to-dot.  Later pages for the same image have fewer and fewer dots.  This teaches how to draw.

The last dot or number before a discontinuity is marked with some symbol indicating pick up your pen and restart at the next number.  A picture does not have to be a single continuous line.

[fqdnhwqh] Even versus odd dimensions

Enumerate geometric things which behave differently depending on whether the number of dimensions is odd or even.  Inspired by algorithms in computational geometry.

[dccpeblm] CNN CA

Convolutional neural networks and cellular automata like Conway's Game of Life seem like a good fit, but not sure exactly how.  Maybe spaceship searches and design, searches for other interesting objects, or design of universal circuits and constructors.

Sunday, February 25, 2018

[xucvjwda] Pari/GP first-stage ECM time

Number of seconds pari/gp's factorint function spends on other algorithms before trying MPQS for factoring numbers of various sizes (in bits).  Most of that time is spent on the Elliptic Curve Method.  Hardware and software info:

Intel(R) Core(TM)2 Duo CPU E8600 @ 3.33GHz
GP/PARI CALCULATOR Version 2.9.4 (released)
amd64 running linux (x86-64 kernel) 64-bit version
compiled: Jan 16 2018, gcc version 5.4.0 (Funtoo 5.4.0)
threading engine: single

for(n=95,151,p=precprime(2^n);q=precprime(p-1);T=gettime();factorint(p*q,9);print(2*n," ",(gettime()-T)/1e3))


One additional data point from a different computer and different software version: 299 bits (10^90-81), 5767.238 s.

Friday, February 23, 2018

[gmiuenaz] Base 30

Yet another partial attempt (another attempt) at creating something like MIME quoted-printable, a way of encoding any Unicode code point using only printing 7-bit ASCII characters while still keeping English text vaguely readable (so not say Base64 applied to UTF-8).  If there's anything I've learned, there are many ways to do this.

We want the letters a-z to keep plain text readable; let's choose lowercase.  We want space, though maybe we want to use underbar or period as space (similar to URL encoding using plus as space).  We want an escape character, say semicolon (;).  We choose it because it is on the home row on QWERTY keyboards.  Add parentheses because matched delimiters are useful if we want to encode hierarchical structure.  This yields 30 characters.  We could do more, but for simplicity start here.  Previously similar.

Similar ideas: if the escape character were backslash (\), text would look like C strings or LaTeX.  If the escape character were ampersand (&), text would look like HTML.

Characters that are not the lowercase letters or space are encoded in two possible ways:

  1. Long Parenthesized escape sequences ;(something)
  2. Short escape sequences ;lowercase

Let's choose uppercase to have short escape sequences, specifically the escape character followed by the letter repeated: ;aa ;bb...  Numerals should be similar, though there's a choice between (a=0 ... j=9) or (z=0, a=1 ... i=9).  The former sorts better; the latter follows models like Greek and Hebrew which have used letters as digits though perhaps not in place-value systems.  (Or we could just add 0-9 to the 30 letters.)  Let's choose 0=;z ;a ;b... ;i=9.  Numerals get the second shortest escape sequences.

Short escape sequences in general start with semicolon followed by a sequence of lowercase letters.  How should a short escape sequence end?  Several possibilities we could choose: a space, the escape character again, or the sequence of lowercase letters encodes its endpoint.  The latter is what UTF-8 (very roughly) does: the high bit in each byte indicates we're still in an escape sequence.  More generally, the escape sequence could traverse a Huffman-tree-like structure where in we know we've hit a leaf because we know the structure of the tree.

Variations possible: if we had more than 1 escape character, then different escape characters could be the root of different trees.  UTF-8 could be interpreted as having 128 escape characters.

Let's choose short escape sequences to end with either a space or the escape character again, but the latter signifying the start of another escape sequence.  This keeps compact things like digit sequences.  It does introduce a few awkwardnesses: the encoding of a character requiring an escape sequence followed by a character not requiring one will awkwardly have a space in it: camelCase = camel;cc ase.  A character requiring an escape followed by a space awkwardly needs to be encoded with two spaces after it: the capital letter ;aa  has decimal ;aa;ss;cc;ii;ii  value ;f;e .

Short escape sequences are reminiscent of HTML entity references, though the latter use characters beyond a-z, like uppercase.  They also explicitly mark the end of a reference with a special character, semicolon.

There is no difficulty in finding the end of a Long Parenthesized escape sequence so long as we enforce that parentheses match.

The escape sequence of semicolon immediately followed by a space is uniquely the shortest escape sequence.  Let's keep it unassigned; maybe it gets used by the UI to signify something special like leaving typing mode (similar to vi), or the user can assign it.

At this point, all that remains is to assign escape sequences to the all the rest of the Unicode code points.  Long escape sequences permit many schemata, each preceded by a schema identifier.  One possible schema is a formula to convert back and forth between a Unicode code point number and a digit sequence in base 26.  It's not strictly a number is base 26 because leading "zeroes" (the letter a?) matter.  Use the formula for the sum of a finite number of terms of a geometric series.  Unfortunately, some will spell out vulgar words.

Long parenthesized escape sequences also intriguingly permit a rich Lisp-like language with different combinators for expressing the how a complex Unicode character is put together from components.  This requires the structure of complex Unicode characters be broken down into their component parts.  This probably already exists.  Previously, thoughts on Japanese and investigation into Korean (Hangul).