Friday, January 13, 2017

[kemfqqdz] Magnetic levitation

There are two major types of magnetic levitation for trains.

Electromagnetic levitation: German Transrapid, Shanghai Maglev.

Electrodynamic suspension: two subtypes.

With superconductors, relying on diamagnetism: JR Maglev

Without superconductors, relying on ferromagnetism: Inductrack, Hyperloop.

It is very surprising that the superconductor subtype was developed (to a working full-scale prototype) before the non-superconductor version.  Superconducting magnets seem much more expensive and difficult.

[bwootzwo] Minesweeper scratch ticket

Minesweeper is the best puzzle to be made in physical form in the style of a scratch ticket.  (Not good for the actual lottery; people will repaint incorrectly scratched mines if money is riding on it.)  Perhaps it can be included as a fun irrelevant puzzle in lottery tickets.

What other puzzles would work?

Sudoku as scratch ticket might be a good way to temporarily conceal then deliver the solution.  It could include "mines" of squares that are not solvable by logic, though that might be a tricky thing to define.  Perhaps a sudoku that does not have a unique solution.

[xjujmpsg] Randomly discarding most odd numbers being tested for primality

The common but bad algorithm to find a random large prime number (e.g., for RSA) is first to generate a large number x, then test in order x, x+1, x+2,... until a prime is found.  This is bad because it is not uniform: it will preferentially select primes with large prime gaps preceding them.  We do not know yet if this bias causes significant cryptographic weakness.  GnuPG uses this algorithm, as of 1.4.21.

The right way to fix this is to generate complete new random numbers for each number tested for primality.  However, this consumes a lot of entropy.

We can partially repair the problem as follows: test numbers in order starting from x as before.  However, before testing a number for primality, reject it outright with high probability, perhaps 0.999.  Then, only 0.1% of numbers will be tested for primality, which will skip over many actual primes, so avoid many starting x's mapping to the same found prime x+i.

The pseudorandom number generator used for sampling the 0.1% probably does not have to be very good, so it can be quick, so very little computing time will be spent rejecting numbers.  Most of the computing time will be primality testing.

How good is this repair?  How strong does the sampling PRNG need to be?  Does it need to be cryptographically strong?

Another way to do it might be to select a large random-sized jump to each new number to be tested.

[ntmxyalx] Least common multiple of the first N integers

We give the size of the number in bits, so logarithm base 2 of OEIS A003418 Previously.

p=1 ; for(i=1 , 733 , p=lcm(i , p) ; printf("%d %d ; " , i , floor(log(p) / log(2))))

Omitting repeated values for compactness (log of A051451):

p=1 ; for(i=1 , 733 , g=gcd(i,p) ; if(g!=i , p=p*i/g ; printf("%d %d ; " , i , floor(log(p) / log(2)))))

2 1 ; 3 2 ; 4 3 ; 5 5 ; 7 8 ; 8 9 ; 9 11 ; 11 14 ; 13 18 ; 16 19 ; 17 23 ; 19 27 ; 23 32 ; 25 34 ; 27 36 ; 29 41 ; 31 46 ; 32 47 ; 37 52 ; 41 57 ; 43 63 ; 47 68 ; 49 71 ; 53 77 ; 59 83 ; 61 88 ; 64 89 ; 67 95 ; 71 102 ; 73 108 ; 79 114 ; 81 116 ; 83 122 ; 89 129 ; 97 135 ; 101 142 ; 103 149 ; 107 155 ; 109 162 ; 113 169 ; 121 172 ; 125 175 ; 127 182 ; 128 183 ; 131 190 ; 137 197 ; 139 204 ; 149 211 ; 151 218 ; 157 226 ; 163 233 ; 167 240 ; 169 244 ; 173 251 ; 179 259 ; 181 266 ; 191 274 ; 193 282 ; 197 289 ; 199 297 ; 211 305 ; 223 312 ; 227 320 ; 229 328 ; 233 336 ; 239 344 ; 241 352 ; 243 353 ; 251 361 ; 256 362 ; 257 370 ; 263 378 ; 269 386 ; 271 395 ; 277 403 ; 281 411 ; 283 419 ; 289 423 ; 293 431 ; 307 439 ; 311 448 ; 313 456 ; 317 464 ; 331 473 ; 337 481 ; 343 484 ; 347 492 ; 349 501 ; 353 509 ; 359 518 ; 361 522 ; 367 531 ; 373 539 ; 379 548 ; 383 556 ; 389 565 ; 397 573 ; 401 582 ; 409 591 ; 419 599 ; 421 608 ; 431 617 ; 433 626 ; 439 634 ; 443 643 ; 449 652 ; 457 661 ; 461 670 ; 463 679 ; 467 687 ; 479 696 ; 487 705 ; 491 714 ; 499 723 ; 503 732 ; 509 741 ; 512 742 ; 521 751 ; 523 760 ; 529 765 ; 541 774 ; 547 783 ; 557 792 ; 563 801 ; 569 810 ; 571 820 ; 577 829 ; 587 838 ; 593 847 ; 599 856 ; 601 866 ; 607 875 ; 613 884 ; 617 893 ; 619 903 ; 625 905 ; 631 914 ; 641 924 ; 643 933 ; 647 942 ; 653 952 ; 659 961 ; 661 970 ; 673 980 ; 677 989 ; 683 999 ; 691 1008 ; 701 1017 ; 709 1027 ; 719 1036 ; 727 1046 ; 729 1047 ; 733 1057 ;

[nqxjypxr] Tunable urandom

On Linux, /dev/random blocks when high quality random bits are not available, but /dev/urandom continues to emit "only cryptographically strong" bits even if it hasn't been able to mix in entropy for a long time.

Wanted is something tunable in between: it blocks when the ratio of entropy in and bits out decreases below some user-specified threshold.

[dvaklhhl] Falsify the present

Trollishly create false records of the present, your present, so that future researchers and historians will puzzle over them or perhaps blindly accept them as truth.

Falsifying the present seems easier than falsifying the past, because the past requires access to historical records.

What kinds of false records will the future be most likely to be gullible to?  Perhaps ask current historians what types of records of the past they struggle to find or verify.

Coming soon will be significant climate change.  Record what life is like before climate change.

Tuesday, January 10, 2017

[sxisqanh] Is it live or is it Memorex?

Under what conditions is it preferable to consume or experience and event live instead of a sound or video recording?

The biggest difference of "live" is that it is social: you consume simultaneously with others around you.  When does that matter?  How does that matter? 

There are a few other technical differences that are rapidly being eliminated by technology, e.g., VR.

[fcpxjrfj] Opposition to death penalty

There are those who oppose the death penalty because it is too cruel.  There are others who oppose it because it is not cruel enough: lifetime imprisonment is believed crueler so better -- we have a very vindictive society.

In places which have abolished the death penalty, how much was the reason for abolishing it the latter reason?

Those who believe prison should be cruel provide the political force for mistreatment of prisoners by guards or by fellow inmates.  Stand idly by and let it happen.

[lavljmgv] Fixing leap seconds

The obvious solution to avoid time going backward at the leap second is to deploy a separate time standard which monotonically counts forward, so it is TAI except expressed as a number.  We will need a new set of system calls to get and set that number.  We probably need to augment NTP to distribute that number. 

Computers can internally count the new number, or internally count UTC as they currently do.  They can provide both system calls, converting between them depending on which system call is invoked and what they internally count.  New and updated software should use the new system call, but the old system call can be provided indefinitely for backward compatibility.  New systems should internally count the new number.

Smearing the leap second over (say) a day is less than ideal because time will disagree with computers not smearing.  It may also interfere with tasks needing a time interval to high precision.

The new number should be significantly different from the POSIX counter (Unix time) so that if one is accidentally substituted for the other, it will be obvious.  Previously, we proposed a fanciful 835-bit wide number, which avoids needing to encode floating point and will probably never need to worry about overflow.

There is something wrong about attempting to politically end leap seconds when this kind of non-disruptive software solution exists.

[wvrnupbd] Rogue planets

During the formation of a solar system, there are lots of planets which haven't organized themselves into stable orbits yet, so many planets probably get ejected.

At the end of its lifetime, a star undergoes mass loss which probably destabilizes planetary orbits (e.g., by breaking resonance structures) causing more planets to become ejected.

How dense is space with planets unattached to stars?  Also comets, of course.  Navigation hazard?

[qgppohzt] Brotli text generator

Invert the language model hardcoded into the Brotli compression algorithm to turn it into a random text generator.

Monday, January 09, 2017

[lvbetgkb] Right section of a function

A left section of a binary (two-argument) function is easy to write in Haskell using partial function application: just omit the last (right) argument.  A right section is a little bit more awkward, requiring backquotes, lambda, or flip.

import Data.Function((&));

-- example binary function (not an operator)
f2 :: a -> [a] -> [a];
f2 = (:);

-- we will use the larger functions later
f3 :: Int -> a -> [a] -> [a];
f3 _ = (:);

f4 :: Bool -> Int -> a -> [a] -> [a];
f4 _ _ = (:);

test :: [String];
test = map (\f -> f 'h') -- all of these evaluate 'h':("el"++"lo") yielding hello
[ (`f2` ("el" ++ "lo")) -- backquotes (grave accents) are inline operator syntax. An inline operator followed by an argument, all surrounded by parentheses, is operator right section syntax: one is supposed to imagine a hole in front of the backquotes: (__ `f2` ("el" ++ "lo"))
, (\arg1 -> f2 arg1 ("el" ++ "lo")) -- lambda syntax
, (\arg1 -> f2 arg1 $ "el" ++ "lo")
, ((flip f2) ("el" ++ "lo"))
, ((flip f2) $ "el" ++ "lo")
, (flip f2 $ "el" ++ "lo")
, (flip f2 ("el" ++ "lo")) -- It might be a little surprising that this one works, if one had thought of "flip" as a function taking only one argument, namely the function to be flipped. However, because of currying, it actually takes 3 arguments. flip :: (a -> b -> c) -> b -> a -> c.
, ("el" ++ "lo" & flip f2)

-- For these 3- and 4-argument cases, we would like to create a lambda on the penultimate argument.
-- , (`f3 (2 + 3)` ("el" ++ "lo")) -- This does not work because the contents of the backquotes must be a binary function that is a single token, not an expression.
, (let { t2 = f3 (2 + 3) } in (`t2` ("el" ++ "lo")))
, (\penultimate -> f3 (2 + 3) penultimate ("el" ++ "lo"))
, (\penultimate -> f3 (2 + 3) penultimate $ "el" ++ "lo") -- this wordy lambda syntax is one of the best in terms of low parenthesis count and avoiding deep parentheses nesting.
, (flip (f3 (2 + 3)) ("el" ++ "lo")) -- similar to "a little surprising" above
, (flip (f3 (2 + 3)) $ "el" ++ "lo")
, (flip (f3 $ 2 + 3) $ "el" ++ "lo")
, ((flip $ f3 (2 + 3)) $ "el" ++ "lo")
, ((flip $ f3 $ 2 + 3) $ "el" ++ "lo")
, ("el" ++ "lo" & (f3 (2 + 3) & flip))
, ("el" ++ "lo" & (2 + 3 & f3 & flip))

, (\penultimate -> f4 (not True) (2 + 3) penultimate ("el" ++ "lo"))
, (\penultimate -> f4 (not True) (2 + 3) penultimate $ "el" ++ "lo")
, (let { t2 = f4 (not True) (2 + 3) } in (`t2` ("el" ++ "lo")))
, (flip (f4 (not True) (2 + 3)) ("el" ++ "lo"))
, (flip (f4 (not True) (2 + 3)) $ "el" ++ "lo")
, ((flip $ f4 (not True) (2 + 3)) $ "el" ++ "lo")
, ((flip $ f4 (not True) $ 2 + 3) $ "el" ++ "lo")
, ("el" ++ "lo" & (f4 (not True) (2 + 3) & flip))
, ("el" ++ "lo" & (2 + 3 & f4 (not True) & flip))
, ("el" ++ "lo" & (2 + 3 & (not True & f4) & flip))

(\f -> f 'h') could have been written ($ 'h') , a right section itself, but we deliberately avoid being potentially obscure in the test harness.

Friday, January 06, 2017

[kzpybzhu] Paragraph separators in Gmail android app

Write two paragraphs of text as a message on different phones and examine the HTML that actually gets sent.  (Easiest done at the receiving end.). There is something terribly wrong with how the newer Nexus 5x does it.

This affects blog-by-email for this blog, and makes GnuPG unable to parse PGP ASCII armor.

<div dir="auto">Nexus<div dir="auto"><br>
</div><div dir="auto">5x</div></div> 

Android version: 7.0
Android security patch level: November 5, 2016
Baseband version: M8994F-
Kernel version: 3.10.73-g5a3d8a9
Build number: N5D91L


Google Keyboard

<p dir="ltr">Galaxy</p>  <p dir="ltr">Nexus</p> 

Android version 4.2.2
Baseband version I515.10 V.FK01 / I515.FK02
Kernel version 3.0.31-g9f818de
Build number JDQ39


Google Keyboard

[jardjvop] More bagpipe

Take the principle of a bagpipe, air supplied by mouth but pressure supplied by arm, and create other wind instruments, probably louder than current versions with pressure supplied by mouth and lungs.

Unfortunately it will probably lose the great facility of embouchure.

[rfwkfqbs] No duals

Test whether the solution to a mate in N chess problem has no duals.  I think this means, on every path of most resistance (there may be multiple such paths because the defender could defend multiple ways) the attacker has a unique move to complete mate in N.  If the defender makes suboptimal moves, then the attacker's best moves need not be unique.

Perhaps relax the constraint toward the end when it is mate in 1 or 2.  Or some sort of clearly winning position in a "play and win" problem.

Wednesday, January 04, 2017

[oqgqulke] Capitalized punctuation

Capitalize `{|}~ to get @[\]^ according to the ASCII table (alter 1 bit).  DEL maps to _

Apply a similar transformation to the digits 1..9 to get !"#$%&'() and 0 maps to space.  This is almost, but not quite, the shifted numerals on the keyboard.  Beyond 9, we also have :;<=>? shiftable to *+,-./

Shift the other way to map 0-9 to P-Y.

  ! " # $ % & ' ( ) * + , - . / 
0 1 2 3 4 5 6 7 8 9 : ; < = > ? 
@ A B C D E F G H I J K L M N O 
P Q R S T U V W X Y Z [ \ ] ^ _ 
` a b c d e f g h i j k l m n o 
p q r s t u v w x y z { | } ~ ⌂

Tuesday, January 03, 2017

[uaskrdtz] Mapping letters to numbers in ASCII

A way to map letters to numerals, based on the ASCII table printed 32-wide, is 0 .. 9 = P .. Y. This is a bit surprising; one might have expected the digits to line up with the beginning of the alphabet.  The digit block does line up with a multiple of 16.

It suggests adding Z for base 11.

[kghqxjsk] Malcolm X as Old Testament

The Old Testament is about customs of tribes, tribes defining their identity (often through military victories and losses).

Malcolm X spoke of black identity, and using that identity as a foundation for political strength. 

The New Testament is about breaking down the tribal barriers and uniting around broader concepts like compassion.

Martin Luther King, Jr., a Christian minister by training, spoke of people of different races united as brothers and sisters.

The debate between them is very, very old.

Monday, January 02, 2017

[xvafqsgw] Default text color and background

Try setting the default text color and background in a web browser (e.g., Firefox) to light on dark to see how many web pages become unreadable.  Many webpages specify either a dark text color or (xor) a light background color but not both, causing either dark-on-dark or light-on-light when one changes the defaults to light on dark.  Light on dark is useful in dark ambient environments.

The ability for users to set their default colors and fonts seems to be disappearing from browsers, though still present in desktop Firefox.  User stylesheets are also useful.

[nhstyeva] Loopiness of a season

Given a collection of games between players (or teams), find as many nontransitive loops as possible, e.g., A beats B, B beats C, C beats A.

Such loopiness may signal a well-designed sport: there are many ways to win, many ways to lose.

[xevirvht] gpg setpref string

gpg --edit-key

setpref S9 S10 S13 S8 S12 S7 S4 S11 S3 S1 S2 H11 H9 H10 H8 H3 H2 H1 Z0 Z3 Z2 Z1 mdc no-ks-modify

This translates to (showpref)

Digest: SHA224, SHA384, SHA512, SHA256, RIPEMD160, SHA1, MD5
Compression: Uncompressed, BZIP2, ZLIB, ZIP
Features: MDC, Keyserver no-modify

Principle on ciphers and digests: Be liberal in what you accept.  This is much more ciphers and digests than the default preferences.  It is hard to imagine, but if a sender wants to send you something but can only use some weird but still-believed-to-be-secure ciphers, there's no reason to stop them.  I suppose it does open you up to exploits in rarely used code paths as you decrypt.

Prefer ciphers with larger keys over smaller keys.  Prefer ciphers with larger block sizes over smaller.  Prefer AES family over other less scrutinized ciphers.  Prefer Bruce Schneier ciphers because maybe his popularity has caused his ciphers to be more scrutinized.

Digests (hash functions): prefer digests which do not dump their entire state.  Prefer shorter digests over long, because that affects message size.  (I suppose cipher key size also affects message size.)  Accept MD5 because collision attack is not applicable.

Compression: prefer no compression because compression can leak information about the plaintext.  But if you are going to use compression, then use the best one.

The list of features available appears not to be documented anywhere.  Reading the source code, 1.4.21, those are the only two features available.

Beware that in 1.4 and 2.0, setting the preferences of a secret key, then exporting then importing the secret key will reset the preferences to default.

Finally, consider increasing the number of password hashing iterations protecting your private key.

[wmlnpsuf] Most efficient universal CA computer

Given a specification of a universal cellular automata, for example Conway's Game of Life, what is the most efficient implementation of a universal (Turing-complete) computer in it?

Considerable subjectivity: different measures of efficiency (e.g., compactness or number of generations per clock tick), and different computations to run on implemented universal computer.

Minimize the Life Unit Cell needed to simulate itself.

Sunday, January 01, 2017

[yactpuij] Observations of the leap second

The following script documents the system clock going backward at the leap second.

for (( i=0 ; ; i++ ))
do echo -n $i" "
date --iso=ns

Feed into gzip or bzip2 or xz then kill the script process by PID (not ^C, because that will kill the compression program).

Ubuntu 14.04

13293621 2016-12-31T18:59:59,996480552-0500
13293622 2016-12-31T18:59:59,998502752-0500
13293623 2016-12-31T19:00:00,000424730-0500
13293624 2016-12-31T19:00:00,002255494-0500
13293625 2016-12-31T19:00:00,003949090-0500
13293626 2016-12-31T19:00:00,005448105-0500
13293627 2016-12-31T18:59:59,007054958-0500
13293628 2016-12-31T18:59:59,008465206-0500

Ubuntu 16.04

45948121 2016-12-31T18:59:59,999325546-05:00
45948122 2016-12-31T18:59:59,999808163-05:00
45948123 2016-12-31T19:00:00,000337888-05:00
45948124 2016-12-31T19:00:00,000877926-05:00
45948125 2016-12-31T19:00:00,001407343-05:00
45948126 2016-12-31T19:00:00,001934319-05:00
45948127 2016-12-31T19:00:00,002418765-05:00
45948128 2016-12-31T19:00:00,002899595-05:00
45948129 2016-12-31T19:00:00,003372363-05:00
45948130 2016-12-31T18:59:59,004051384-05:00
45948131 2016-12-31T18:59:59,004808767-05:00

The following script is described here.  We can observe the repetition of 23:59:33 as the system clock goes backward (as above), then later 23:59:60.

for (( i = 0 ; ; i++)) ; do echo -n $i" " ;TZ=right/UTC date --iso=ns ; sleep 0.33 ; done

56853 2016-12-31T23:59:31,198116288+0000
56854 2016-12-31T23:59:31,530940907+0000
56855 2016-12-31T23:59:31,863877362+0000
56856 2016-12-31T23:59:32,196930593+0000
56857 2016-12-31T23:59:32,529740731+0000
56858 2016-12-31T23:59:32,863085326+0000
56859 2016-12-31T23:59:33,196001280+0000
56860 2016-12-31T23:59:33,528957882+0000
56861 2016-12-31T23:59:33,862031907+0000
56862 2016-12-31T23:59:33,194771050+0000
56863 2016-12-31T23:59:33,527665662+0000
56864 2016-12-31T23:59:33,861096024+0000
56865 2016-12-31T23:59:34,194124683+0000
56866 2016-12-31T23:59:34,527900279+0000
56867 2016-12-31T23:59:34,861187587+0000
56940 2016-12-31T23:59:59,175893786+0000
56941 2016-12-31T23:59:59,508957877+0000
56942 2016-12-31T23:59:59,841721314+0000
56943 2016-12-31T23:59:60,174499990+0000
56944 2016-12-31T23:59:60,507358020+0000
56945 2016-12-31T23:59:60,840145798+0000
56946 2017-01-01T00:00:00,173087257+0000
56947 2017-01-01T00:00:00,506015576+0000
56948 2017-01-01T00:00:00,838836886+0000

Future project: observe what happens to the RTC (hwclock).

Saturday, December 31, 2016

[aamtoufg] Observing the leap second (at the wrong time)

First, find out what time the leap second will occur in your local timezone:

$ date '--date=TZ="right/UTC" 2016-12-31 23:59:60'
Sat Dec 31 19:00:26 EST 2016

Then, as that time approaches:

$ TZ=right/EST date

You can substitute right/UTC for right/EST if you wish to see the leap second in UTC.  You can also substitute things like right/America/New_York.

Simulation of what should happen, by artificially setting the date:

$ TZ=right/EST date '--date=TZ="posix/EST" 2016-12-31 19:00:25'
Sat Dec 31 18:59:59 EST 2016
$ TZ=right/EST date '--date=TZ="posix/EST" 2016-12-31 19:00:26'
Sat Dec 31 18:59:60 EST 2016
$ TZ=right/EST date '--date=TZ="posix/EST" 2016-12-31 19:00:27'
Sat Dec 31 19:00:00 EST 2016

Note well, this will mark the leap second some 26 seconds after it actually occurs.  Details of why in the previous post. Also more information about the "right" timezone database.

You may also wish to add --iso=ns (nanoseconds) to date, or wrap the whole thing in a loop:

while true ; do ... ; done

Or add a sleep 1.

Observing the leap second at the wrong time has the benefit that the computer has settled down to a steady state by then, so you won't see additional weird things happening as the leap second actually occurs, as the computer resets its system clock.  One can try something hacky like the following to cause __:59:60 to display at the actual leap second,

$ TZ=right/EST date --date=@$(( $(date +%s) + 27 ))

but the computer behaves weirdly at the actual leap second. The above command will be 1 second too fast before the leap second, hold 18:59:60 for 2 seconds (the latter of which is the actual leap second), then be correct after the leap second.  Changing to +26 will be correct before the leap second, hold 59:59 for 2 seconds (including during the leap second), display 59:60 (1 second after the leap second), then continue to be 1 second slow afterwards.  Here is a simulation of +27:

$ TZ=right/EST date --date=@$(( $(date '--date=TZ="posix/EST" 2016-12-31 18:59:58' +%s) + 27 ))
Sat Dec 31 18:59:59 EST 2016
$ TZ=right/EST date --date=@$(( $(date '--date=TZ="posix/EST" 2016-12-31 18:59:59' +%s) + 27 ))
Sat Dec 31 18:59:60 EST 2016
$ TZ=right/EST date --date=@$(( $(date '--date=TZ="posix/EST" 2016-12-31 19:00:00' +%s) + 27 ))
Sat Dec 31 19:00:00 EST 2016

Another silly hack: if one is going to observe the leap second at the wrong time, then one might as well observe it at local midnight.

$ TZ=right/UTC date --date=@$(( $(date '--date=TZ="posix/EST" 2016-12-31 23:59:59' +%s) + 26 - 18000)) '+%r %Y'
11:59:59 PM 2016
$ TZ=right/UTC date --date=@$(( $(date '--date=TZ="posix/EST" 2017-1-1 0:00:00' +%s) + 26 - 18000)) +'%r %Y'
11:59:60 PM 2016
$ TZ=right/UTC date --date=@$(( $(date '--date=TZ="posix/EST" 2017-1-1 0:00:01' +%s) + 26 - 18000)) '+%r %Y'
12:00:00 AM 2017

The following script will try to tick the seconds at the correct time with subsecond precision:

while true ; do while [[ $(date +%N) > 090000000 ]] ; do : ; done ; TZ=right/UTC date --date=@$(( $(date +%s) + 26 - 18000)) '+%r %Y' ; sleep 0.9 ; done

Update: Some actual observations.

Wednesday, December 28, 2016

[bhqpyemy] These values are not pi

? log(640320^3+744)/sqrt(163)
? Pi

? log((640320^3+744)^2-393768)/2/sqrt(163)
? Pi


[vuptqpwg] Demonstration of RSA in Pari/GP

We demonstrate 16384-bit RSA below, slightly larger than the size (15360) recommended by NIST for the security level equivalent of 256-bit AES (symmetric) encryption.  Encryption (equivalently signature verification) was pretty fast (averaging 0.79 milliseconds (790 microseconds) over repeated trials).  Decryption, with its much larger exponent, is much slower, though still tolerable (0.76 seconds).

We generate p and q with precprime, obviously not random, because it is a compact and easy way to get a large prime number.  It also provides example timings of how long it might take to find a 8192-bit prime number.  The purpose \g5 is to catch if or when Pari/GP is trying to do a large futile factorization.  (Aside: it will try to do such a factorization when f is computed as f=eulerphi(n).  But this can be made to complete in 537 milliseconds by preceding it with addprimes(p).)  The most significant magic is the inversion of e modulo f, where f is not a prime.

GP/PARI CALCULATOR Version 2.7.5 (released)
amd64 running linux (x86-64/GMP-6.0.0 kernel) 64-bit version

? #
timer = 1 (on)
? s=2^8192
? p=precprime(s)
time = 34,720 ms.
? q=precprime(p-1)
time = 42,080 ms.
? p-s
? q-s
? n=p*q
? f=(p-1)*(q-1)
? \g5
debug = 5
? e=65537
? gcd(e,f)
? d=lift(Mod(e,f)^(-1))
? lift(Mod(e,f)*Mod(d,f))
? c=Mod(10^40,n)^e
time = 4 ms.
? lift(c^d)
time = 829 ms.
? x=0;for(i=1,10,x=x+Mod(random(n),n)^d)
time = 7,569 ms.
? x=0;for(i=1,10000,x=x+Mod(random(n),n)^e)
time = 7,901 ms.
? \q
$ cat /proc/cpuinfo
model name : Intel(R) Core(TM) i5-4690S CPU @ 3.20GHz

Saturday, December 24, 2016

[nxhebfuc] 34 characters for English

A ... Z
thorn eng ampersand
( ) #

Parentheses -- a matched pair of delimiters -- allow hierarchically structured text.  Most obviously, sentences, paragraphs.

The number sign # functions like an escape character.  #a ... j map to digits (probably like #cegab).  #k and beyond might be common punctuation and other things for escaping, e.g., formatting, capitalization.  #( ... ) is intriguing.

The parentheses suggest that text encoded using these characters should actually be interpreted as Lisp program that emitting Unicode or more structured text.  Lisp makes common use of dash in identifiers to separate words (note CamelCase is not available in our encoding because no capitalization), but we also don't have dash.  Maybe identifiers are permitted to have spaces and every atom is surrounded by parentheses.  Or weirdly use apostrophe as a separator.  Or distinguish between one and two spaces.  Or identifiers with spaces are surrounded by a special form.  Or  add a dash or underscore, increasing to 35.

34 (or 35) is a bit larger than nice 32, though changing base is not a big deal.  Fitting within 36=6*6 might be useful.

[hknbgvds] Append B

Take a word or message (without spaces) and interpret it as value in base 26, encoded little endian: a=0, b=1,... z=25.  Messages ending in an arbitrary number of a's cannot be distinguished from each other, analogous to invisible leading zeroes: 7 and 007 are the same big-endian decimal value but have different meanings.

Standard trick to solve this problem (e.g., seen for binary messages for MD5 and SHA-1): append a "b" to the end of the message (most significant digit), then convert the little-endian message to a value.  When decoding a value, strip the trailing b.

Other simple ideas: permit spaces in the message and use space=0, a=1,... z=26.  Trailing spaces get lost, which might be fine.  If big-endian, then leading spaces get lost.

Having converted a message to a value, proceed with, e.g., encryption.  Computers can compute radix conversion very quickly.

Converting a value to an output encoding in some base is easy.  If leading zeroes are again relevant, convert first to binary then to the target base.

Inspired by the awkwardness of needing base 32 for a simple cipher .  This encoding may grow the message by a letter or two, so not quite fitting in the original template.  (Of course, one would never keep the original message template for real encryption.  Use some other template.)

Friday, December 23, 2016

[atlnktkv] Four movement keys

Movement keys needed on touchscreens: left right home (beginning of line) end (of line).  Up and down are less needed; fingers can point with reasonable precision vertically because characters are tall.  Inspired by the Google Android keyboard (Gboard) which provides left/right navigation by sliding on the spacebar, but could use home and end.  A very long single line text field (URL) needs lots of scrolling to reach the beginning.


[knkpgwyf] Precognition in a game

One can simulate precognition, a character with the ability to see the future, in a game by allowing the player to roll back time (undo).  Probably helpful if opponents are deterministic.  Then play the time stream as performance.

Inspired by Jedi.

[ehitzrcs] Prime generating sequence

Is the computationally most efficient way to find a prime number of a given (large) size to search either for a Mersenne prime (Lucas-Lehmer) or test random numbers with some other well-known general prime number test (probably slower than LL by only a constant factor)?  (Consider trying to win the EFF Cooperative Computing Award.)  Can this be proven?

A counterexample might be an easy-to-compute sequence that is significantly denser in primes than simply the integers filtered by sieving.  Prove no such sequences exist.

[xnrnnfbo] Double predation

The cat has been stalking the mouse.  It pounces, but in the midpoint of its pounce, the cat gets picked off in midair by a large predatory bird or other larger predator which had been stalking the cat.

[uaouyxpg] Darth Vader as Terminator

Depict Darth Vader as an unstoppable unassailable archvillain in a story taking place slightly before Star Wars Episode 4.  The rebels are justifiably scared shitless of him.

Inspired by criticism of Rogue One.

Monday, December 19, 2016

[xrzqvpap] Shaped text

Any text can have its spacing, punctuation, and capitalization altered to match that of another template text.  Not sure what this might be useful for, perhaps a red herring to throw off cryptanalysis.

Aaaaaaaa aaaaa aaaa aa aaa aaaaaaaaaa aa aaaaaaaaaaaaa aa aaaaaaaa, aa aaaaaaaaaaa aaa aaaa aaaaaaaa aaaaaaa; aa aaaaaaaaa aaa aaaaaaa aa aaaaaa, aa aa aaa aaaaa; aa aaa aaaaa aa aaa aaaaaa aaaaaaaaa aa aaaaaaaa, aaa aa aaaaaaaa aaa Aaaaaaaaaa aaa a aaaaaaa aa aaaaaaaaaa.

Below are 676 digits of the square root of 26, expressed in base 26.

Fcoyjobw xilky rtoh vk auh zedskehhup gj sijceekmbkyct pz rnryxgod, fn vmcwaflvtwm anx cwqa zdssfhnp biwmzqg; yz qrbaskigw gla ovaewrz ry paovvi, se yu yvz jcjua; ns kin naqgk rj zlo fkmawm snrnwchns mi peoywtwx, zpq eu ifpaaaag bop Pynztcaubp ivr u htdmmdf au tottjmkzaq.  Oyilmswk dtxzt ouiy pc ill plyhcjiebb ba udaeosjqkyrls fs pcttqana, tb vwynrdefmcu rdb ebyj tcvxvwhf wgazyya; ei bmylkbeso zcq xmbghrl pn yyhxkx, tm az edh rbwfn; wc tru zpdtx oi xuk omglbo puhfvtxdx fq cgyihcgo, pcn so vzhrshsk esk Oiejnnqqnf ktx x kdybkrh ct cfhmxagkfk.  Fjublacd zpdhh luam dy zvw bklkxxegju qj iuofdjhgezynz eu dkrqyeob, wg smpaotpxvmn vth mprl chxgblwh bcpnfdi; oy koqtnhiyg yas zoioawb xx uimdfq, ly fb lza vfntd; eo khi wbkef hc krj sywuyh ryudavaci uj zvtvsvqe, shl nc oaeofxuu rnr Xycfcathfy eal x ygwlkqx ns vrzchdfmgc.  Scthvbpv uy

The template text is the First Amendment, used previously, cycled as many times as necessary.

Source code in Haskell.  We create a "template" describing the pattern of capitalization and punctuation, then zip it with text, except we do not use zip, but instead unfold (unfoldr), because punctuation elements in the template do not consume any text, so zip does not quite work.

Friday, December 16, 2016

[ripsdmzo] Equality of algebraic numbers

Given two algebraic numbers, determine if they are equal; equivalently, given an algebraic number, determine if it is equal to zero.

Intuitively, this problem seems difficult, perhaps intractable.  However, if the algebraic number is specified as a polynomial with integer coefficients, it does not seem so hard: is the constant term zero?  Perhaps the difficulty is in specifying which root of the polynomial.

[yyqaqeer] Instant factoring

What is the largest size general numbers which can be factored "instantly" according to human perception?  Provide it as a function in a calculator app (but it is a function that returns multiple values).  (Actually, returning just the least prime factor would be useful.)

Which algorithm should be used?  The crossover point where the number field sieve becomes more efficient than quadratic sieve is probably way beyond the timescale of "instant" so NFS will not be needed.  Experiments with Pari/GP find that quadratic sieve does produce useful results within 100 milliseconds.

We want a highly optimized parallel implementation to take advantage of multicore.  (This is the only failing of Pari/GP.)

Trying other algorithms leads to messy questions.  Other algorithms, e.g., elliptic curve method, tried before quadratic sieve can decrease average running time but will increase worst case running time.

The only factorizations useful for most people are probably either less than around 10000 (or smooth so that all factors are less than 10000) or greater than 2^1024 (the latter effectively impossible), so providing quick factorizations of medium sized numbers is probably overkill.

[ujpfhpfl] Comparing Brotli text compression with gzip xz bzip2

Original file is a highly repetitive log file of software compiling.

116530086 h10.log
 15689146 h10.log.bro1
 13353595 h10.log.gz
 13150100 h10.log.gz9
  7636694 h10.log.bz2
  7277693 h10.log.bro9
  6632700 h10.log.xz
  6327414 h10.log.bro10
  5905125 h10.log.bro11
  5905125 h10.log.bro
  5706828 h10.log.bro-w24

gz9 is gzip -9.  broN is bro with -q N.  Brotli defaults to --quality 11 (the maximum), which is a fun reference to Spinal Tap, but is highly unintuitive compared to every other compression program which only goes up to 9.  And brotli has no manpage or usage documentation (true to Google style) to find this out.  bro-w24 is bro -w 24.

[rjmvxijx] Bending the fundamental forces

Significantly modify "Avatar: The Last Airbender" so that the 4 elements are not earth, air, water and fire, but the 4 fundamental forces of nature, gravity, strong nuclear force, weak nuclear force, and electromagnetism.  Benders who can manipulate those forces can do amazing things.  Certain benders can manipulate more than one, unifying some forces in the order seen in reality, and the rarest bender, the avatar, has unified all 4, analogous to the Theory Of Everything.

[kplnpdhr] Find positions which engines differ

Given two chess engines, find positions about which they significantly disagree on evaluation.  This might be a good task for machine learning.

Then, of course, improve the engine which is making the bad evaluation.

[elhqodnx] The Bible advocating modern genocide

Extract quotes of the Bible advocating or celebrating genocide and replace the names of the targets/victims with whoever extremists want to genocide this week.  (This of course is already being done.)  Deuteronomy 7, Deuteronomy 20, Joshua 11, 1 Samuel 15 is the most explicit.

Particularly poignant might be to modify it in the original language: Masoretic Text.

[rtmtblnr] Star Politics

Take just the politics aspect of The Phantom Menace dial it up to 11, making a whole movie about political maneuverings in a galactic government.  It initially might seem to be the worst idea ever, but perhaps not so bad: space politics as an allegory for human politics on planet earth.

Every deal, every decision, affects trillions of beings or more.

[lybrkesb] Testing all Chess960 initial positions

When inventing Fischer Random Chess, did Bobby Fischer carefully analyze all 960 initial positions to make sure none were hugely unbalanced (e.g., white has a forced line that can gain winning advantage, or black can easily force a draw)?  If so, that is impressive Edison-level perspiration that very few people could have done in the days before chess engines.

There were also the rejected chess variants that didn't end up becoming Chess960.

[udcchqhe] Argon2 4TB limit

The Argon2 password hashing algorithm has a hardcoded 4 terabyte (tebibyte) maximum limit of memory it can be specified to use.  This seems like a terrible idea -- the limit (if any) should be much higher.  Can Argon2 be easily extended to use more memory?

There are computers right now that have over 4 TB of RAM (granted, they are supercomputers) and that much RAM or more will likely become more accessible in the near future.  (The addressable limit -- currently 8 TB for amd64 -- will also likely increase.)  Furthermore, even if they don't become commonplace, an organization for whom security is very important might get a single expensive computer dedicated to password hashing, making attacking a hashed password very expensive for adversaries.

Repeating the Bill Gates mistake: N units [of memory] should be enough for everyone.

[cdalfncq] Encrypting with a visual puzzle

In addition to encrypting sensitive data with a password, also consider additionally encrypting it in a way that requires solving a CAPTCHA-like puzzle.  Details remain about how to implement it and what the UI should look like.

Threat model: the legitimate user already knows what documents he or she wants to access, so can go directly to it, solving a few CAPTCHAs.  The illegitimate user -- e.g., surveillance or forensics -- wants to scan the entire computer or system or stream for something but will have to solve a CAPTCHA for each item -- each file -- scanned.


[nfypbdyk] Multicore compression

Two ways to parallelize data compression:  Compress multiple different blocks in parallel, or have multiple different cores working on the same block, perhaps exploring different ways to compress the block.  The latter is not done too much, but could be and should be: there are some extremely slow but powerful compression algorithms out there that do significantly better than what is widely available.  Maybe parallelization will exhaust memory before exhausting number of processor cores.

[dbcpqerb] Cantor hypercomputer hierarchy

A hypercomputation does an infinite amount of computation in finite time; perhaps each clock cycle is half the length of the previous one, in the style of Zeno's paradox.  (Such a computer cannot realistically be built.)  This can, say, test a property over all integers or all rational numbers.  Supertask.

More powerful would be to test over all real numbers.  More powerful would be to test over all functions over real numbers.  And so on up the Cantor hierarchy of infinities: aleph or beth numbers.

Which computer can calculate the halting probability of a random Turing machine?  I think "all possible Turing machines" is a countable set, and of course the number of cycles a Turing machine runs is also countable.

When a powerful computer capable of testing over all reals or functions runs, what does its output look like?  Find me a noncomputable real number, we tell it.  OK, here is one, it responds, but what does this output look like?  Perhaps the text string "the halting probability of a random Turing machine".

Monday, December 12, 2016

[lkuzxate] Who to have more babies?

Suppose a country, for example, Japan, is struggling with negative population growth, and wants to provide incentives for people to have more children.  How should the incentives be structured?  In particular, should it be designed to result in many families having slightly more children, or a few families having many more children?

The latter might be more efficient through economies of scale but potentially causes problems with only a small number of parents defining the culture of the next generation.

[jsvxprhp] Pong circular paddle

In the classic computer game Pong, the angle the ball bounces off the paddle depends on where on the paddle the ball hits.  This could be nicely illustrated by making the paddle shaped like a semicircle.

Several difficulties: the bounce point is no longer strictly on the back wall -- the plane of a flat paddle; it may be separated from the back wall by the radius of the paddle.  Should the momentum of the paddle become transferred to the ball?  If so, how much?

[vqkiasgc] Jigsaw puzzle as captcha

It seems there ought to be a way to make jigsaw puzzle solving into a good CAPTCHA, because humans have strong priors on what the world looks like.

Perhaps show two non-adjacent pieces of an image and challenge the solver to put them in their approximately correct relative orientation.  Maybe rotations too.

Saturday, December 10, 2016

[ujvufhwd] Links for LSJUMB members and alumni


LSJUMB Alumni Facebook group

Currently the old mailing list still works, however, just in case, there's a new Alumni google group and marching unit thinkers google group, set up by Ben Serebrin CPG/Altoz 99-03.

Jilliane Bruffey writes that all the lsjumb- mailing list addresses are being backed up, so if the old mailing lists stop working, they will probably subscribe everyone to the new mailing lists.

Tuesday, December 06, 2016

[ngwvdwgc] Comic strip CAPTCHA

Put these cartoon panels in an order that makes a coherent story.

Monday, December 05, 2016

[uutfauve] Clear Sox

Can the Red Sox please choose a new name which does not endorse and glorify the hated Republican party (or Communist Party)?

Of course, the baseball team's affiliation with the color red was chosen long before the color took on its present negative connotation.  However, the present negative connotation is real, so it can be argued that teams of the present must adapt to culture and norms of the present.

Similar arguments are being made about the Cleveland Indians or other Native American mascots, where the meaning has changed over time, again because of politics.

[lbidjeth] Ranch dressing on French fries

A variation on the controversial mayonnaise on French fries.

Thursday, December 01, 2016

[opeaxcpi] Big ball sports

Consider modifying a ball sport by making the ball much larger.  Many other things will likely need to change.

Wednesday, November 30, 2016

[rzagbygj] Warping an image

Smoothly warp an image.  This is probably a diffeomorphism, a very practical one.  Can arbitrary diffeomorphisms be approximated by combining simpler objects like the way splines can approximate arbitrary curves and surfaces?

Consider a vector field joining  the "before" and "after" location of each pixel.  Approximate small patches of the vector field (somehow) by discretely sampling it and interpolating a function over the patch, then glue these patches together in a way that preserves smoothness.

[ccmbrcbp] Finite speed of gravity in the solar system

When Earth feels a tug of Jupiter's gravity as it passes it on the inside, is it feeling where Jupiter is now, or where Jupiter was when the gravitational force left Jupiter, traveling at the speed of light toward earth?

Is the typical and naive gravitational simulation with instantaneous gravity incorrect?  I'm guessing it is correct, though explaining the illusion of instantaneous gravity will take some thought.

[vyrbklgi] Time management game theory

Time management in chess, both for computers and humans, does not seem to have well established principles like minimax and alpha-beta search.  Distill time management into an incomplete information game, removing the chess aspect.  Each player begins with a certain amount of "effort", and operates on a probability distribution, perhaps bell curve.  On each turn, a player can expend effort to modify (or perhaps learn?) the parameters of the probability distribution.  At the end of the game, the distribution is sampled to determine the winner.

Many details yet to be worked out.

Spending a lot of effort early is a bet that the game will not be long.

[wsszqdiv] Two visual layers of information

Black text on various-colored background.  Could have two independent streams of information, or they could be related / synchronized (Previously vaguely related).  Need a way of encoding information as a color pattern (and people need to learn to read it).

Easiest is low resolution illustration.

[wiiaulrc] Bender

We imagine a segmented powered device which bends metal tubes from the inside into complex shapes.  It is interesting how a 1-dimensional object can become 3-dimensional.  Inspired by protein folding.

Similar ideas: the powered device forms the desired shape in air, serving as a scaffold, then the tube is constructed around it, perhaps a pumped resin that hardens around the scafford, or precast segments transported then welded into place.

[bbaylkev] Coriolis force on a tethered balloon

Launch a tethered balloon at the equator (perhaps also at the poles for comparison).  Can the Coriolis effect be measured either in the upward centrifugal force or the angle of deflection?  A balloon high up must travel further than the ground to make one revolution around the earth.

[fkjobmao] Ring theory

Wikipedia gives an impressively long sequence of class inclusions:

commutative rings ⊃ integral domains ⊃ integrally closed domains ⊃ GCD domains ⊃ unique factorization domains ⊃ principal ideal domains ⊃ Euclidean domains ⊃ fields ⊃ finite fields

For each step, precisely describe the change and give examples which are in a class but not its subclass.

[ojlyxzsh] Known Rubik's solve

Consider a Rubik's cube solving competition in which the scramble is published far in advance, providing contestants with the opportunity to learn and practice solving it as fast as possible.

Obviously a short solving sequence found by computer is good, but the human contestants might prefer a slightly longer one that is easier to execute rapidly.

For larger cubes, both discovering a short solving sequence and memorizing it may be interesting challenges.  Perhaps prefer a longer sequence that is easier to memorize.

[xqbmjraq] Packing algebraic numbers

The solutions (parameters) to circle packing within a circle or square are probably algebraic numbers (even if the packing is only known to be locally optimal).  Specify these algebraic numbers alongside their picture, perhaps as polynomials with integer coefficients.

[uehzakkk] Difficulty of factorization

Given a Unique Factorization Domain, when is factoring computationally difficult like it is (or seems to be) with the integers?  Actually, factorizations might not need to be unique to be computationally difficult to find even one.

[vvtilfue] Prove that it works

The typical way mathematical proof is taught in education is unpleasant, perhaps partly due to the pointlessness of it.  Adjust it by introducing proofs with tangible outcomes:

Easiest is computer programs: Prove that the program works and does not crash.  A geometric proof might be used to show that a mechanical device will actually do what it is supposed to do.  Such proofs are more satisfying: the effort in proving it had a point.

Unfortunately most engineering is not done with mathematical rigor.

[psxggbnv] Evolution of psychological memory

You cannot consciously change what you like or dislike (especially, are disgusted by).  This instinct is partially helpful: a bad experience can lead to disgust (possibly through trauma) which will help you avoid it in the future, without having to consciously recall the details of the bad experience.

However, this instinct is also the basis of a tremendous number of ways people can be socially manipulated.  It is somewhat surprising that evolution has deemed it to be more good than bad.

What, if anything, should a nanny state do to protect people from being manipulated in ways that humans are biologically programmed to be susceptible to?  (Should it limit speech?)  If social pressures select for people who are less susceptible to manipulation, this may decrease the effectiveness psychological memory, which may have long-term consequences on human evolution.

[lhzfamml] Effectiveness of the cartridge box

One of the arguments against gun control is that an armed populace safeguards liberty, prevents the government from becoming tyrannical.  Objectively, how effective is it?  A tricky thing to measure, the number of violent revolutions prevented.

"Governments should be afraid of their people." (V for Vendetta)

Many liberals fear the tyranny of the upcoming Trump presidency.  Should they be arming themselves?  Selling guns right now to Muslims and other soon-to-be-oppressed groups seems like a profitable venture.

Fear of the upcoming tyranny may be effective in explaining opposition to gun control to those formerly in favor of it.

[fvjcccjx] Unexpected presidency revealing puppeteers

The election of Trump caught many commoners by surprise.  Did it also catch any powerful people by surprise?  Are there powerful people and entities who would like to remain hidden or unnoticed but are now needing to pivot rapidly to survive or thrive in the new political situation?  Does such rapid pivoting reveal them?

[wpdvkvkk] Heptatonic fun

Given a song that uses only the notes in a heptatonic scale (no accidentals), it can easily be transposed (by note number in the scale) to all keys and modes (including alternate heptatonic scales).  Many of the transpositions may sound pretty weird.  Multiple voices allow modal counterpoint.

Ascending melodic minor = heptatonia secunda; descending = natural minor / Aeolian mode.

[avwkaxre] Predicting Obama martial law

When Obama was elected in 2008, the fringe right predicted he would declare himself dictator-for-life, refusing to step down at the end of his term, destroying the American democracy.

With Trump elected, the fringe left, or perhaps even the mainstream left, would prefer Obama do exactly that (perhaps holding new elections with Trump and Trump clones made ineligible, perhaps through assassination).

In 2008, did the fringe right make a prediction as to how a large number of Americans would come to support, or at least stand idly by, democracy hypothetically being destroyed?  Were they correct in the predicted mechanism by which they would become convinced?

[aigfrdxb] Jumping on a graph

Checkers can be generalized to any graph.  Color the edges.  A jump enters from an adjacent node, captures the piece on the node, and exits by another edge the same color as the inbound edge.

More fancy stuff: directed edges, different edges (same nodes) for different piece types.


[xyahdvvi] Kanji in ASCII

Create an ASCII text description of Chinese characters that (in principle) can be read by people.

One way: standardized vocabulary (in some ASCII renderable language) of radicals and way of describing the position of a radical within a character. First disambiguation suffix: a number by stroke count.  Second disambiguation suffix: a number by commonness.

It will be very cumbersomely long.

[ejvcrbcp] Variations on jumping

Rule possibilities on jumping and capturing for games like checkers:

Multiple jumps (chained jumps) permitted or forbidden.

Is a player required to capture if capturing is possible?  No captures required, at least one jump required (not required to make multiple jumps beyond the first), multiple jumps required (but player has option of which multiple jumps) until no more jumps possible, the multiple jump which captures the most pieces is required.

For a game like Lasca in which a piece does not necessarily disappear after being jumped once, are multiple jumps over the same piece in a loop permitted?

[lvvgphfj] Avoiding mirror strategy in replicated games

When playing multiple simultaneous games in the style of combinatorial game theory (game sum), an easy way to avoid mirror strategy is to have different boards have different initial positions, like Chess960.

[mvtobfjv] Memorizing the best pi approximation

Memorize just that e^(pi*sqrt(163)) is almost a perfect cube, and its difference from a perfect cube is almost an integer.  The other constants can be derived.

First calculate the cube root of the "almost integer".  Note exp(x/3) = cbrt(e^x).

? exp(Pi*sqrt(163)/3)

Then find the offset from the cube.  Note that many scientific calculators do not have enough internal precision to compute this correctly.

? exp(Pi*sqrt(163))-640320^3

Then you have recovered the necessary ingredients for the formula, which yields 30 correct digits of pi.  One did not have to memorize 640320 or +744.

? \p50
   realprecision = 57 significant digits (50 digits displayed)
? log(640320^3+744)/sqrt(163)-Pi
2.23735150380481508416601318272292512584 E-31

A similar memorization: sqrt(58) ... perfect 4th power yields 18 digits.

We can get 46 digits with a little more work, memorizing 2*Pi*sqrt(163) and perfect square:

? exp(Pi*sqrt(163))

? exp(Pi*2*sqrt(163))-262537412640768744^2

Note 393768/2 = 196884 is Monstrous Moonshine.  Skip the next 2 steps if one already found 640320 and 744 from above.

? sqrt(exp(Pi*2*sqrt(163))+393768)^(1/3)

? sqrt(exp(Pi*2*sqrt(163))+393768)-640320^3

? log((640320^3+744)^2-393768)/(2*sqrt(163))-Pi
-9.303470618546941055 E-47

Of course, it is a little bit silly to be using a high-precision value of pi to compute a lower-precision approximation of pi.  Furthermore, if one is memorizing a formula for pi, easiest would be to memorize 4 atan 1 which gives an infinite number of correct digits.

Monday, November 28, 2016

[xxneozpu] Demonstration of Data.Numbers.Fixed

Here is a little demonstration of arbitrary precision floating-point (actually fixed-point) arithmetic in Haskell, using Data.Numbers.Fixed in the numbers package.  Using dynamicEps, we calculate sqrt(1/x) to arbitrary precision, outputting the number in a user-specified base.

Performance is not so great; the package implements Floating functions using elegant but not necessarily high performance algorithms based on continued fractions (Gosper, HAKMEM).  The hmpfr package might be better.  (For square root, it might also be easy to roll one's own implementation of Newton's method on Rational.)

Radix conversion of a fractional number is implemented as an unfold, similar to radix conversion of an integer.

Thursday, November 24, 2016

[odwlmxqk] Lists versus sets in grammars

Wherever there is an asterisk in a grammar, denoting zero or more repetitions of a production, say whether order semantically matters in the repetitions.

(If order doesn't matter but repetitions of identical items matter, then bag or multiset.)

Inspired by function ordering within a file mattering in C, but not in many later languages.

[fsyidptc] Deleting all public references

Consider adding to the Anyone Can Censor sharing site a seemingly ridiculously draconian feature that any published URL to content on the sharing site that the sharing site owner can find will have the linked content censored, killing the link.  Finding publicly published URLs to a site can be done with a search engine.

At first glance, it seems the site owner is defeating the popularity of his or her own service.  However, such a policy or feature might help promote the growth of trust networks, so that URLs to content are only disseminated along trusted covert paths.  Those who want to censor content can typically find it only when published.

URL link shorteners easily defeat this, but that might be OK.

[ijeciwqn] Network and CPU load

Decrease the bandwidth or increase the latency of a device's, e.g., smartphone's, network connection.  I strongly suspect this causes increased CPU load or memory usage as apps and tasks that would have completed quickly with a faster network stall and pile up.  This is unfortunate, as the foreground task might have no network interaction whatsoever, but gets slowed by a slow network.

[onfophfd] Find the missing card

All but one item of a set is shown simultaneously but shuffled.  The winner is the one who identifies the missing item first.  Or, instead of one missing, one duplicated item.

Create an input method to fairly judge the race.  25 items suggest an input method of one button pressed per hand (one button assigned to each finger).

[eufsxvbu] Fanfic ascended

The original author offers to edit and improve fanfics.  A liberal license like Creative Commons would be very useful.

[bneanpnh] How severe should business cycles be?

Less severe business cycles decrease the suffering during depressions or recessions, but bad large business are more likely to survive them, preventing innovative changings of the guard.

[rboaqvao] Phone manufacturers

A list of some large smartphone manufactuers, after cursory research:


[gcnbudzm] Dueling mojo

Got My Mojo Workin' (Asylum Street Spankers) ends similarly to the beginning of Dueling Banjos (Theme from Deliverance).  Mashup.

[eqsdkhiw] Nature amplified

Universal rule of art: take something people are already familiar with and modify it, making it "better".  Apply the rule to nature, depicting modified nature in virtual reality.

Take a photorealistic VR helicopter tour of a more awesome waterfall than exists on Earth.  Vaguely inspired by Niagara Falls being artificially rate limited.  Also inspired by the "Amplified" Minecraft terrain option.

[ruzomkls] Smoother numbers

Given two numbers, which is smoother?  This is mostly an aesthetic question; there is no right answer.  Start by comparing their largest prime factor.  The one with the larger prime factor is less smooth.

If they are the same, we could compare their second largest prime factors, equivalently comparing the smoothness of the two numbers divided through once by their common largest prime factor.  Here is that ranking of smoothness of numbers 1 through 99:

1 2 4 8 16 32 64 3 6 12 24 48 96 9 18 36 72 27 54 81 5 10 20 40 80 15 30 60 45 90 25 50 75 7 14 28 56 21 42 84 63 35 70 49 98 11 22 44 88 33 66 99 55 77 13 26 52 39 78 65 91 17 34 68 51 85 19 38 76 57 95 23 46 92 69 29 58 87 31 62 93 37 74 41 82 43 86 47 94 53 59 61 67 71 73 79 83 89 97

Alternatively, if two numbers share the same largest prime factor, then declare the smaller number smoother.  Here is such a ranking for 1-99:

1 2 4 8 16 32 64 3 6 9 12 18 24 27 36 48 54 72 81 96 5 10 15 20 25 30 40 45 50 60 75 80 90 7 14 21 28 35 42 49 56 63 70 84 98 11 22 33 44 55 66 77 88 99 13 26 39 52 65 78 91 17 34 51 68 85 19 38 57 76 95 23 46 69 92 29 58 87 31 62 93 37 74 41 82 43 86 47 94 53 59 61 67 71 73 79 83 89 97

Inspiration is that smooth numbers might more memorable.  The perfect powers might be memorable 0 1 4 8 9 16 25 27 32 36 49 64 81.  Let the more important or more frequent public transit bus routes have the more memorable numbers.

Alternative or more complicated criteria possible.  Smoothness of exponents: 2^2^2^2 seems smoother than (say) 2^13.  64 seems smoother than 32.  Number of factors or divisors.  Squarefree numbers might be considered smoother, then avoiding multiple squared prime factors, then avoiding cubes, etc.

[yglwlarn] Chess annotation chat

Consider chat about a chess game limited only to variations and annotations, e.g., Numeric Annotation Glyphs.  Also add the ability for people to agree or disagree with an annotation, a meta annotation.  Are other types of meta annotations needed?

Some way of rescinding annotations and meta annotations.

[ksvzgrpc] Hilbert curve text

Lay text out on a page as a Hilbert curve, so that words near each other in "time" (as if spoken) tend to be near each other in space (on the page).

Easiest is a grid of letters with lines or walls (like a maze) to guide the eye.  Or maybe smoothly changing background colors.

More complicated is to create a new alphabet designed to be written in the highly twisty Hilbert curve.  Morse code might be a good start.  Electrical capacitor symbol.  Thin line with large dot.  Triangles of various colors pointing to the next letter.  Thin line becoming thick, or double line.

Vaguely inspired by boustrophedonic writing sytems.

[ksvzgrpc] Jump into the middle of a function

Consider a programming language which permits calling functions to start running (have an entry point) at any point in the function, controlled at the call site.  Perhaps more radically, the call site can perform arbitrary code manipulations on a function before calling it.  It probably needs to be an interpreted language.

Slightly tricky might be to define the function type signature for such modified calls.

This decreases the need to refactor, or at least the for the function/library author to refactor: the caller -- the function caller -- can do the refactoring.  A demo program can quickly be reused as a library.

Sunday, November 20, 2016

[djekhfwt] Hash size affects result

We modified the Stockfish chess engine to store a 64-bit key (up from 16 bits) in each transposition table entry (TTEntry).  Previously.  This effectively raises the hash key size to at least 76 bits, so there should be approximately no hash collisions.  Nevertheless, the size of the hash table affects the result of the computation to a given fixed depth.

The transposition table is not acting strictly as memoization.  If it were strictly memoization, then a smaller hash size would simply result in repeated computation, taking longer to compute to a given fixed depth, but the same answer.

Source code.

Logs demonstrating the issue.

Future: measure which memory size is stronger (for a given fixed depth) with a head-to-head match.

Thursday, November 17, 2016

[ntwzztae] Stockfish arbitrary hash size

By default, the Stockfish chess engine can only have the memory use for its transposition table be a power of two number of bytes.  This is inconvenient because most computers come with exactly a power of two amount of memory (and for Macs, this cannot be upgraded).  One cannot give the entire memory to the engine, leaving none for the operating system, but leaving almost half of it unused is also undesirable.

However, by modifying the source code, and possibly sacrificing performance, one can fine tune the memory use to any size.  Adjust ClusterSize in tt.h, possibly remove the padding, and possibly also disable the static assertions that it fit in a cache line.

ClusterSize is the maximum depth of the linear separate chaining, in hash table terminology, so avoid making it too large.

[kwyvloxk] Legislative deals

Would government be improved by providing legislators mechanisms to make more complicated deals with each other?

Perhaps any and all votes within a legislative session may be rescinded.  Or, somewhat equivalently, the legislatures votes on exactly one mammoth bill at the end of the session.  Not sure how votes on amendments to bills should work.

[cptggwey] Load balancing with subdomains

Consider a protocol in which a client is not provided with a full host name to connect to, but a domain name.  The client is supposed to generate a random host name to prefix in front of the domain name.  The server's DNS can be configured to provide an IP addresses for any host name.  This provides a client-driven mechanism for load balancing, which seems somewhat less sleazy than the current common method, in which one host name gets mapped or redirected to multiple different IP addresses, with load balancing baked into DNS.

With the clients generating nonces, we lose the benefit of the DNS fabric being permitted to cache.  Perhaps the client checks a few agreed-upon common hostnames first, then if those are down or slow, creates a random one.

[bpzzpxsc] Chess in jail

Prisons are one place which can implement fairly draconian measures to prevent players from cheating using computers.

[nclzdccu] Replenishing the lower classes

The lower classes, constantly working the system to achieve upward class mobility, will have some members, often of the next generation, succeed.  However, assume society needs a fixed size (or fixed proportion) lower class population, probably for labor.  Enumerate the methods used in various societies of keeping the lower classes sufficiently populated counteracting losses due to upward movement, probably methods of class demotion.

Forbidding abortion might be one: unplanned pregnancy, especially with single mother, may demote both mother and future child.

Wednesday, November 16, 2016

[bwraaqjk] Security updates

Users can choose their favorite mirror for package updates of Debian and Ubuntu, but everyone is funneled through or for security updates.

This seems like a bad idea.  An attacker can deny a user access to security updates by attacking the user's DNS, preventing them from resolving security.{...}, or redirecting it to a site not containing a security update the attacker intends to exploit.  Attacking DNS to prevent or spoof the resolution of just one name seems easier than preventing the resolution of every possible mirror (including unpublished ones) a user might have chosen.

Furthermore, an attacker eavesdropping DNS can estimate who has taken security updates and who hasn't (and target the latter for attack) by monitoring who resolves and accesses security.{...}.

[cdhqseis] Shiny plate

Create a dinner plate that is shiny like a mirror and resists scratching, tarnishing, or corroding (or poisoning).

Easiest might be glass over aluminum, like a typical mirror.

Tuesday, November 15, 2016

[jzmyrjkx] cksum of zeroes

Results of cksum on files consisting only of null bytes.  File sizes 1, 3, or 5 times a power of 2. File sizes up to 8796093022208 bytes (8 TiB) were generated in their entirety with dd if=/dev/zero .  It turns out a null byte does not change the internal state of the checksum algorithm (CRC-32), so sizes larger than 8 TiB were simulated with this program which processes only the size appended as a suffix to the (null) data.

Not sure what this is useful for: a file of zeros can easily be verified by reading it.

Previously, with MD5 and SHA1.

4294967295 0
4215202376 1
4135437457 2
4072462630 3
3975907619 4
3896153236 5
3849957965 6
3656847943 8
3497339177 10
3404948635 12
3018728591 16
2699711059 20
2514929975 24
1742489887 32
1104454823 40
734892655 48
3413741448 64
2271761656 80
1398421864 96
2532515601 128
248556017 160
2725605222 192
4215202376 256
3128462852 320
2041723600 384
4135437457 512
1961958409 640
4072462630 768
3975907619 1024
3896153236 1280
3849957965 1536
3656847943 2048
3497339177 2560
3404948635 3072
3018728591 4096
2699711059 5120
2514929975 6144
1742489887 8192
1104454823 10240
734892655 12288
3413741448 16384
2271761656 20480
1398421864 24576
2532515601 32768
248556017 40960
2725605222 49152
4215202376 65536
3128462852 81920
2041723600 98304
4135437457 131072
1961958409 163840
4072462630 196608
3975907619 262144
3896153236 327680
3849957965 393216
3656847943 524288
3497339177 655360
3404948635 786432
3018728591 1048576
2699711059 1310720
2514929975 1572864
1742489887 2097152
1104454823 2621440
734892655 3145728
3413741448 4194304
2271761656 5242880
1398421864 6291456
2532515601 8388608
248556017 10485760
2725605222 12582912
4215202376 16777216
3128462852 20971520
2041723600 25165824
4135437457 33554432
1961958409 41943040
4072462630 50331648
3975907619 67108864
3896153236 83886080
3849957965 100663296
3656847943 134217728
3497339177 167772160
3404948635 201326592
3018728591 268435456
2699711059 335544320
2514929975 402653184
1742489887 536870912
1104454823 671088640
734892655 805306368
3413741448 1073741824
2271761656 1342177280
1398421864 1610612736
2532515601 2147483648
248556017 2684354560
2725605222 3221225472
4215202376 4294967296
3128462852 5368709120
2041723600 6442450944
4135437457 8589934592
1961958409 10737418240
4072462630 12884901888
3975907619 17179869184
3896153236 21474836480
3849957965 25769803776
3656847943 34359738368
3497339177 42949672960
3404948635 51539607552
3018728591 68719476736
2699711059 85899345920
2514929975 103079215104
1742489887 137438953472
1104454823 171798691840
734892655 206158430208
3413741448 274877906944
2271761656 343597383680
1398421864 412316860416
2532515601 549755813888
248556017 687194767360
2725605222 824633720832
4215202376 1099511627776
3128462852 1374389534720
2041723600 1649267441664
4135437457 2199023255552
1961958409 2748779069440
4072462630 3298534883328
3975907619 4398046511104
3896153236 5497558138880
3849957965 6597069766656
3656847943 8796093022208
3497339177 10995116277760
3404948635 13194139533312
3018728591 17592186044416
2699711059 21990232555520
2514929975 26388279066624
1742489887 35184372088832
1104454823 43980465111040
734892655 52776558133248
3413741448 70368744177664
2271761656 87960930222080
1398421864 105553116266496
2532515601 140737488355328
248556017 175921860444160
2725605222 211106232532992
4215202376 281474976710656
3128462852 351843720888320
2041723600 422212465065984
4135437457 562949953421312
1961958409 703687441776640
4072462630 844424930131968
3975907619 1125899906842624
3896153236 1407374883553280
3849957965 1688849860263936
3656847943 2251799813685248
3497339177 2814749767106560
3404948635 3377699720527872
3018728591 4503599627370496
2699711059 5629499534213120
2514929975 6755399441055744
1742489887 9007199254740992
1104454823 11258999068426240
734892655 13510798882111488
3413741448 18014398509481984
2271761656 22517998136852480
1398421864 27021597764222976
2532515601 36028797018963968
248556017 45035996273704960
2725605222 54043195528445952
4215202376 72057594037927936
3128462852 90071992547409920
2041723600 108086391056891904
4135437457 144115188075855872
1961958409 180143985094819840
4072462630 216172782113783808
3975907619 288230376151711744
3896153236 360287970189639680
3849957965 432345564227567616
3656847943 576460752303423488
3497339177 720575940379279360
3404948635 864691128455135232
3018728591 1152921504606846976
2699711059 1441151880758558720
2514929975 1729382256910270464
1742489887 2305843009213693952
1104454823 2882303761517117440
734892655 3458764513820540928
3413741448 4611686018427387904
2271761656 5764607523034234880
1398421864 6917529027641081856
2532515601 9223372036854775808
248556017 11529215046068469760
2725605222 13835058055282163712

[kaigcpee] 4D data visualization

A 2D plot is a 1D value plotted against another 1D value.  We 3D beings can see an entire 2D plot from "above", which is nice.  5D beings could easily see a 4D plot: 2D plotted against 2D, which seems interesting.

[izwwgqom] Rational roots of 2

The cube root of 2 seems close to 1.26 ("26 cents"), but nothing special happens in the continued fraction expansion.

? 2^(1/3)
? contfrac(2^(1/3))
[1, 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, 2, 1, 4, 12, 2, 3, 2, 1, 3, 4, 1, 1, 2, 14, 3, 13]
? contfrac(1.26)
[1, 3, 1, 5, 2]

We explore rational approximations to other roots of 2, truncated before large terms in the CF.  The Pari/GP function contfracpnqn was useful.

4th root 1+7/37

5th root 1+40/269

6th root 1+6/49

7th root 1+28/269 .  This is the second instance of denominator 269.

8th root 1+1/11 or 1+41/453

9th root 1+2/25 = 1.08

10th root 1+1/14

11th root 1+8/123

12th root does not have any nice small rational approximation, despite musical pitches and intervals being based on the twelfth root of 2.  2^(1/12) = 3^(1/19) = 1.5^(1/7)

Create a geometric or mechanical demonstration of these approximations.

From elsewhere:

9.1^(1/4) = 33/19
91000^(1/4) = 330/19

[bxbdewak] A collection of approximations of pi

Number of digits correct:


Later versions of Pari/GP may have to use a different name for this function.

? digits(3.14)

? digits(22/7)

? digits(355/113)

? digits(sqrt(sqrt(2143/22)))

The fraction above can be written 3^4+2^4+1/(2+(2/3)^2) = 9^2+19^2/22 . Previously discussed.

? u=5^4+53*sqrt(89) ; digits(80*sqrt(15)*u^(3/2)/(3308*u-3*sqrt(89)))

? digits(log(396^4-104)/sqrt(58))
Previously discussed.

? digits(12*log((3+sqrt(10))*(sqrt(8)+sqrt(10)))/sqrt(190))

? digits(log(640320^3+744)/sqrt(163))

? digits(log((640320^3+744)^2 - 2*196884)/(2*sqrt(163)))

? digits(log((5280*(236674+30303*sqrt(61)))^3+744)/sqrt(427))

? s=sqrt(17) ; t=sqrt(2) ; a=(23+4*t*s)/2 ; b=(19*t+7*s)/2 ; c=429+304*t ; d=(627+442*t)/2 ; u=q(a)^2*q(b)^2*q(c)*q(d) ; digits(log((2*u)^6+24)/sqrt(3502))

GP allows multiple nullary variables to be defined on a single line, separated by semicolons, but I cannot find a way to also define a function q(x) in a one-liner followed by more variable assignments.  The scope extends to the end of the line, allowing functions with semicolons in them.

Create a mechanical or geometric demonstration of these approximations.

Most of these came from the following two sources.

Monday, November 14, 2016

[qhnbbhqu] Dits and dahs

Consider a binary language in which one character takes up more space than the other.  How many sequences are shorter than a given amount of space?

Inspired of course by Morse code, in which the ratio is supposedly 1/3.

Wednesday, November 09, 2016

[ivdphoee] Cloud block device

Perhaps the best interface for a cloud data storage provider is a block device, randomly accessible by block.  It is up to the user to format this network block device to something useful, like a filesystem with whatever features a user desires.

I know of no cloud data provider which does this.  They all try to be more user friendly, which makes things complicated and difficult.

Simultaneous access remains a thorny problem, though it is squarely the user's (or users') problem now.  The network block device could provide some atomicity primitives.

[ctykdfkh] P2P collaborative

Create a peer-to-peer platform for collaboration.  Instead of a central repository like a wiki (e.g., Wikipedia) or Github, everyone owns a master copy, and the software automatically pulls updates from everyone else's copy to keep things in sync, and makes sure everyone has the most up to date version.

We envision a filesystem interface, so a distributed network filesystem, though probably many other architectures are possible.  Data contention, e.g., merge conflicts, could be handled by the system (maybe locks), higher level tools (maybe storage consists only of messages written in order, never modifying or deleting anything old), or social engineering (they have agreed to collaborate so aren't going to be evil to each other, which is the source of difficult merges).

This might be especially useful for collaboration with large amounts of data, e.g., video, where centralized hosting might be expensive.  However peer-to-peer collaboration with large data will require everyone have high bandwidth and large local storage.

Peer-to-peer synchronization should be encrypted to thwart outsiders from eavesdropping on the collaboration.  Of course authentication also.

[esotcmtl] Recalling a moment of light

There was a brief glimpse of light in the late 90s with the proliferation of P2P software such as Napster, et al., when it looked like the flow of information might not remain controlled by a few giant media companies.  That light got extinguished by lawsuits and legislation, and now we have Facebook, Apple, Google, etc., as well as a few traditional companies controlling most of the media people see, as well as having and exercising powerful editorial ability to restrict what people see.

[rkmgkssw] Climate change caused by life

Climate change caused by humans is minuscule compared to climate change caused by other forms of life in older eras of the earth's history, e.g., Great Oxygenation Event.

This is not an argument against preventing climate change but merely an observation of how little humans are amidst the great forces that shape the universe, and even the planet: bow down to the almighty microorganisms.

Inspired by the hypothesis that continents formed only because of life; if not for life, earth would be an ocean planet.  (Which makes sense: why should there be continents in the face of erosion and minerals tending to dissolve in the "most powerful solvent"?)

[cpzvqzgl] Theo Epstein for President

Made the Red Sox great again.  Made the Cubs great again.

That the same person should be responsible for ending the two longest baseball World Series championship droughts seems an accomplishment without equal, in any field: the Greatest Of All Time.

Perhaps comparable are double Nobel Prize winners.

Epstein twice succeeded at tasks that many before had put in decades of tremendous effort, with tremendous resources, but had failed.  Nobel prize winners are sometimes merely the people who happened to be in the right place at the right time when technology and knowledge of the field advanced just enough to be able to perform an experiment or achieve a result.

That the Cubs' predicament was called the Billy Goat was not a curse; it was a prophecy that the end would be brought about by the GOAT.

(Had Cleveland won, we would be writing the same about Terry Francona.)

[gpnoyhuv] Nice packings of circles in a rectangle

Consider the task of packing N circles (discs) into a rectangle.

Easiest is to arrange the circles in a rectangular array, factoring N = P*Q.  Pick the factorization that fits the rectangular area the best.

Rectangular array with incomplete last row.  There might be some choices about how many circles go in the last row versus the number of circles per row.  The last row can be centered for elegance.

Hexagonal close packing, with rows alternating P, P-1, P, P-1, ... and last row possibly incomplete.  First row could be P-1.  It might not be possible to symmetrically center the last row while maintaining hexagonal close packing.

Hexagonal close packing with all rows (except possibly last) having the same number of circles, but alternatingly shifted left and right.  This arrangement does not have bilateral symmetry, though maybe it does if tilted 90 degrees.

There are other more efficient packings for different values of N, but more irregular.

Inspiration was wanting to pack 128 items into a window for the world's hardest puzzle.

Monday, November 07, 2016

[wisnmyni] Data as a number

Convert a number with possibly many leading zeroes in base M to base N, prefixing the base N output representation with leading zeroes in a way that unambigiously specifies the number of leading zeroes in base M input.  I think this is possible when M > N.  Some potentially useful conversions:

(M=16, N=10); (M=256, N=10); (M=256, N=100); (M=10; N=2)

The deeper idea is, whenever a string of characters represents raw data and not a word in a natural language, it should be encoded so that it is clear that the string is not meant to be interpreted as a word in natural language.  Unannotated hexadecimal fails this rule: if you see the string "deadbeef", is it a word, with a meaning perhaps related to food, or is it a number?  (Annotated hexadecimal, e.g., "0xdeadbeef" is clearly not a word.)  Simpler example: what does "a" mean, indefinite article or ten in hexadecimal?  English, and other orthographies which use Hindu-Arabic numerals, already have a character set which unambiguously state that a string encodes data and not words: the numerals.  (One could argue that numbers -- strings of Hindu-Arabic numerals -- have more meaning than strictly data: they have ordinality, they obey group and field axioms, etc.  However, we frequently see numbers which aren't that, e.g., serial numbers, phone numbers, ZIP codes, ID and credit card numbers.)

The inspiration was, expressing hashes in hexadecimal is silly.  Radix conversion is quick and easy for a computer; it should be in decimal with leading zeroes if necessary.  If making the hash compact is a goal, then base 26 or base 95, with some annotation signifying it is encoded data, is better than hexadecimal.

Some Haskell code demonstrating some of the conversions.

Sunday, November 06, 2016

[ulfdtybu] Transposition table key width

We modified the Stockfish chess engine, changing the width of the key stored in a transposition table entry, the key16 field in TTEntry, from 16 bits to 32 bits.  This changes the key width effectively from 16+27 = 43 bits to 32+27 = 59 bits.  The 27 comes from, in experiments below, hash table sizes such that there were 2^27 Clusters.  The hash table was 3840 megabytes for 16-bit (with padding / alignment disabled, otherwise it would have been 4096), and 4608 megabytes for 32-bit.  Hash 5000 was sufficient for both.

The tables below give the ranking of black responses to 1.e4, as reported by MultiPV 500 at various depths.  The top line is 16-bit unmodified Stockfish, 1 Thread.  The second line is 32-bit.  The colors are randomly assigned to moves.

Snapshot of the code used to generate the output below is on github.  Here is a patch against Official Stockfish 1c0c4db6775fae5a8b785630f4fd406c235880d9. 

This is a work in progress.  In the future, we hope to explore even wider hashes, wide enough that hash collisions do not occur.  We may also explore the region between 16 and 32 bits.

Here are more complete logs, including scores and pv.  "before" is 16-bit; "after" is 32-bit.

Previous work: Hyatt and Cozzie, "The effect of hash collisions in a Computer Chess program", which concludes that collisions do not affect performance much.  However, we feel that with computers having gotten much more powerful, and people running very long analyses, the birthday paradox is having a significant effect, as seen below.  Hash table collisions are obscuring the answer to the question, what is the ground truth about a position?  What is the best response to 1.e4?  Open game, French, Sicilian, Caro-Kann, or Nimzowitsch?

Depth 1


Depth 2


Depth 3


Depth 4


Depth 5


Depth 6


Depth 7


Depth 8


Depth 9


Depth 10


Depth 11


Depth 12


Depth 13


Depth 14


Depth 15


Depth 16


Depth 17


Depth 18


Depth 19


Depth 20


Depth 21


Depth 22


Depth 23


Depth 24


Depth 25


Depth 26


Depth 27


Depth 28


Depth 29


Depth 30


Depth 31


Depth 32


Depth 33


Depth 34


Depth 35


Depth 36