{{ message }}

Instantly share code, notes, and snippets.

Janiczek/01_Exploration of elm-random limits.md

Last active Apr 2, 2022
Exploration of elm/random limits

Exploration of `elm/random` limits

The goal of this exploration is to find out what happens in `Random.int 0 <N>` for various N, particularly along the top end.

The generator says:

Generate 32-bit integers in a given range.

This generator can produce values outside of the range `[minInt, maxInt]` but sufficient randomness is not guaranteed.

But what does that mean exactly? What randomness do we get?

Note that:

• `Random.maxInt` is `2147483647` = `2^31 - 1`
• `Random.minInt` is `-2147483648` = `-(2^31)`

Elm works with JS 64bit floats, which gives it safe integers (`Number.isSafeInteger`) in the range `-9007199254740991..9007199254740991` (`-(2^53 - 1)..2^53 - 1`).

But, presumably because of the specific PCG implementation we're limited to 32 bits. How though?

Let's explore the boundaries.

Macro: Powers of 2

First, I'm going to generate lists of 1000 numbers for `Random.int 0 (2^N - 1)` where `N=1..64`.

ℹ️ I'm using the `- 1` because that seems to be the happy path. Don't worry, I'll explore values that don't fit the happy path too.

ℹ️ I'm using the random seed `0` everywhere.

These files are generated by the `run.sh` Bash script and are named `bits*.txt`.

We can see right away from the sampled numbers and the MD5 hashes that around N=32 we start getting a streak of the same values, duplicated across `N=32..53`, and then a streak of zeros around `N=54..64`:

Thus, the first two insights are:

💡⚠️ It's useless to use `Random.int 0 (2^N - 1)` with `N > 32` (it will bring you no more randomness than with `N = 32`).

💡🚷 It's dangerous to use `Random.int 0 (2^N - 1)` with `N > 53` (the algorithm will give you zeros only).

Our macro-level overview is done, but we still need to zoom into the micro-level view to see where exactly these changes happen, and whether it's safe for us to use at least the `N = 32`, that is, `Random.int 0 (2^32 - 1)`.

Micro: Powers' neighbourhood

To check this, I'm again going to generate lists of 1000 numbers, but this time for specific integers in the neighbourhood of the `2^N - 1`, for `N=31..33`.

These files are generated by the `single.sh` Bash script and are named `single*.txt`.

Interestingly, for `4294967298` (= 2^32 + 2), `Random.int 0 N` takes much longer than for the previous numbers, to the point where I believed it is stuck in an infinite loop of some kind. But nah, it is making progress -- if you generate a list of just 2 numbers, you will get them, it will just take long time. That's why the file `single4294967298.txt` is missing.

Let's plot them:

Around 2^31 we can see the library start to lose its breath: things are mostly the same (but still, ever so slightly changing) as you vary the max integer. The MD5 hashes differ (although above `2^31 - 1` it's not guaranteed), so all is good so far:

But the further up we go, the more problematic things become, duplicates start happening, and we can see that 2^32 - 2, 2^32 - 1, 2^33 - 2 and 2^33 - 1 are identical:

Have you noticed though? The numbers for 2^32 - 1 go up to 4 billion! 🎉

This means the library has managed to give us a roughly uniform range of numbers up to 2^32 - 1! Hey, I'll take that.

I am no cryptographer but from the chart, this range of numbers seems good enough for me for day-to-day use.

We won't have any such luck above that though, because a wraparound happens: at 2^32 we get all zeros, at 2^32 + 1 we get the same result as for 2^1 - 1 (check the MD5 hashes for `bits01.txt` and `single4294967297.txt`!), and the same thing happens around 2^33:

So let's summarize these new insights:

💡♻️ `Random.int 0 n` is roughly the same as `Random.int 0 (modBy (2^32) n)` (if we ignore the weird zeroing behaviour around 2^53 and above): the largest number we can theoretically get out of `Random.int` is 2^32 - 1.

💡🎉 For the maximum range of generated unsigned integers, use `Random.int 0 (2^32 - 1)`.

And that 👆 is the surprising conclusion of this exploration. The range `Random.int Random.minInt Random.maxInt` is there to give you the maximum range of values (`Random.maxInt - Random.minInt + 1 == 2^32`) and both positive and negative integers. If you only care about non-negative ones though, you can use `Random.int 0 (2^32 - 1)` without any perceivable loss of uniformness.

(As in, I didn't need answers to the below for what I need to do, so I'm not gonna bother 😅)

• Do an analogous exploration for the negative numbers. Note that you'll get the "breakpoints" and best performance with `Random.int low high` where `high - low + 1` is a power of 2. My hypothesis is that with `high = 0` the best `low` should be -4294967295 = -(2^32 - 1).
• Vary the initial random seed: do any of the findings change?
• (Purely academical and of no use whatsoever) Why does the zeroing around 2^53 - 1 happen? Where exactly does it happen? Is it only happening for the "almost" powers of 2 or is it happening in all the neighbours too?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/usr/bin/env bash for BITS in {1..64}; do cat << EOF | elm repl | sed -E "s/"\$'\E'"\[([0-9]{1,3}((;[0-9]{1,3})*)?)?[m|K]//g" | sed '1,4d;6d;8d' | sed 's/^> //g' >"bits\${BITS}.txt" import Random import Dict frequencies list = list |> List.foldl (\el counter -> Dict.get el counter |> Maybe.withDefault 0 |> (\count -> count + 1) |> (\count -> Dict.insert el count counter) ) Dict.empty xs = Random.initialSeed 0 |> Random.step (Random.list 1000 (Random.int 0 (2^\${BITS} - 1))) |> Tuple.first frequencies xs |> Dict.toList EOF echo "bits\${BITS} done" done;
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/usr/bin/env bash cat << EOF | elm repl | sed -E "s/"\$'\E'"\[([0-9]{1,3}((;[0-9]{1,3})*)?)?[m|K]//g" | sed '1,4d;6d;8d' | sed 's/^> //g' >"single\$1.txt" import Random import Dict frequencies list = list |> List.foldl (\el counter -> Dict.get el counter |> Maybe.withDefault 0 |> (\count -> count + 1) |> (\count -> Dict.insert el count counter) ) Dict.empty xs = Random.initialSeed 0 |> Random.step (Random.list 1000 (Random.int 0 \$1)) |> Tuple.first frequencies xs |> Dict.toList EOF echo "single\${1} done"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 bits01.txt: [0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,1,0,1,1,1,1,1,0,0,1,1,0,0,1,0,0,0,1,1 bits02.txt: [0,3,2,3,2,3,3,2,1,0,3,2,1,0,3,3,2,2,2,2,2,3,0,1,1,1,1,1,2,0,3,1,2,0,3,0,0,2,3,3 bits03.txt: [4,3,2,7,6,7,7,6,5,4,3,2,5,4,3,7,2,2,6,2,6,7,4,1,1,1,1,1,6,0,3,5,6,0,3,4,0,2,7,7 bits04.txt: [4,3,2,15,14,15,7,14,5,12,3,10,13,12,11,15,2,2,6,10,14,15,12,1,9,9,9,1,14,8,3,13 bits05.txt: [20,19,2,31,14,31,23,14,21,12,3,26,29,28,11,31,2,2,6,26,30,31,28,17,9,9,25,1,30, bits06.txt: [20,19,34,31,14,63,23,14,21,44,3,26,61,28,11,31,2,34,6,26,30,31,28,49,41,9,57,1, bits07.txt: [20,83,98,31,78,63,23,78,21,108,3,26,125,28,75,31,66,34,70,26,94,31,92,113,105,7 bits08.txt: [20,211,226,159,78,191,23,206,21,236,3,154,253,156,75,159,194,34,198,26,222,31,9 bits09.txt: [276,211,226,159,78,191,279,462,277,236,3,410,253,156,75,415,450,34,454,26,222,2 bits10.txt: [276,723,738,159,78,191,279,974,277,236,3,922,765,156,75,415,962,546,454,26,222, bits11.txt: [1300,1747,1762,1183,78,1215,279,974,277,1260,1027,1946,765,1180,75,1439,962,546 bits12.txt: [1300,3795,3810,1183,78,3263,279,974,277,1260,3075,3994,765,3228,2123,1439,3010, bits13.txt: [1300,3795,3810,5279,4174,7359,279,974,4373,1260,7171,8090,765,7324,6219,5535,71 bits14.txt: [9492,11987,3810,5279,4174,7359,8471,974,4373,1260,7171,16282,765,15516,6219,137 bits15.txt: [9492,11987,20194,21663,4174,7359,24855,17358,4373,17644,23555,32666,765,15516,2 bits16.txt: [42260,44755,52962,21663,4174,40127,24855,50126,4373,50412,56323,65434,33533,482 bits17.txt: [107796,44755,52962,87199,69710,40127,90391,115662,4373,115948,56323,130970,3353 bits18.txt: [238868,44755,52962,218271,69710,40127,90391,246734,135445,247020,187395,130970, bits19.txt: [501012,306899,52962,218271,69710,40127,352535,246734,397589,247020,187395,13097 bits20.txt: [1025300,831187,577250,218271,69710,40127,876823,246734,921877,247020,711683,655 bits21.txt: [2073876,1879763,577250,1266847,1118286,40127,876823,1295310,1970453,1295596,176 bits22.txt: [4171028,3976915,577250,1266847,1118286,2137279,2973975,1295310,1970453,3392748, bits23.txt: [4171028,8171219,577250,5461151,1118286,6331583,7168279,1295310,6164757,3392748, bits24.txt: [4171028,16559827,8965858,13849759,9506894,14720191,15556887,9683918,6164757,339 bits25.txt: [20948244,16559827,8965858,30626975,26284110,31497407,32334103,26461134,22941973 bits26.txt: [20948244,16559827,8965858,64181407,59838542,65051839,32334103,60015566,22941973 bits27.txt: [88057108,16559827,8965858,131290271,59838542,132160703,99442967,60015566,900508 bits28.txt: [222274836,150777555,143183586,131290271,59838542,266378431,99442967,60015566,90 bits29.txt: [222274836,419213011,411619042,131290271,59838542,266378431,367878423,328451022, bits30.txt: [222274836,419213011,948489954,131290271,59838542,266378431,904749335,328451022, bits31.txt: [1296016660,1492954835,948489954,1205032095,1133580366,1340120255,1978491159,328 bits32.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits33.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits34.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits35.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits36.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits37.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits38.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits39.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits40.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits41.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits42.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits43.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits44.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits45.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits46.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits47.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits48.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits49.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits50.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits51.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits52.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits53.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 bits54.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits55.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits56.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits57.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits58.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits59.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits60.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits61.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits62.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits63.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 bits64.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 single2147483646.txt: [1296016661,1492954835,948489954,1205032096,1133580367,1340120255,1978491160,328 -- 2^31 - 2 single2147483647.txt: [1296016660,1492954835,948489954,1205032095,1133580366,1340120255,1978491159,328 -- 2^31 - 1 single2147483648.txt: [507935288,301905862,1508815974,471646319,7985536,16793219,1492928418,703311974, -- 2^31 single2147483649.txt: [507935287,301905861,1508815973,471646318,7985535,16793218,1492928417,703311973, -- 2^31 + 1 single2147483650.txt: [507935286,301905860,1508815972,471646317,7985534,16793217,1492928416,703311972, -- 2^31 + 2 single4294967294.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 -- 2^32 - 2 single4294967295.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 -- 2^32 - 1 single4294967296.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 -- 2^32 single4294967297.txt: [0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,1,0,1,1,1,1,1,0,0,1,1,0,0,1,0,0,0,1,1 -- 2^32 + 1 single8589934590.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 -- 2^33 - 2 single8589934591.txt: [3443500308,1492954835,948489954,3352515743,3281064014,1340120255,4125974807,328 -- 2^33 - 1 single8589934592.txt: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 -- 2^33 single8589934593.txt: [0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,1,0,1,1,1,1,1,0,0,1,1,0,0,1,0,0,0,1,1 -- 2^33 + 1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 MD5 (bits01.txt) = fc2504bd79ec05192cfc5cdda15cc7a4 MD5 (bits02.txt) = 781ed8c772b5de14ce50e221a6b0dac2 MD5 (bits03.txt) = ef39f155387708782d6afbc42fa828dc MD5 (bits04.txt) = 37e4950c0a6af673632e957bd3e99285 MD5 (bits05.txt) = 5be09e1741ad0733ba822c449f831ecd MD5 (bits06.txt) = f1c6524fe839965a93bef2c1fa7dc2cb MD5 (bits07.txt) = b290a899033dcd2bfba7d5703d38d115 MD5 (bits08.txt) = 3cfd078d4ca88bfdb936e3a861010e3b MD5 (bits09.txt) = 356d883436f68c9fbfecc2e489b725fe MD5 (bits10.txt) = 0a27350f7cafa84697c4009ebc8b37d9 MD5 (bits11.txt) = b6aa99cd76da79f879b738059343a2f4 MD5 (bits12.txt) = 92184ca5a5f4cd008e1f0bfe1ec39448 MD5 (bits13.txt) = eb1d37ea972e3a186d184a176526dde3 MD5 (bits14.txt) = 743476c5ad522e655d1f8cf49b17d473 MD5 (bits15.txt) = 9699c1d04cc96e74ec2ee86400b61173 MD5 (bits16.txt) = ad44e6ed08347960274bb794fc26469f MD5 (bits17.txt) = a2069b60ef1abdf5e4d322ad82ab1dba MD5 (bits18.txt) = e303fd2b99d41364005095086f263fb6 MD5 (bits19.txt) = d7dcba70a248af21161aca9fcdab69a3 MD5 (bits20.txt) = bb25e50188b519d4750c5ea94ac28f37 MD5 (bits21.txt) = ff5db1908731cfc931bf2bcc9555da18 MD5 (bits22.txt) = bfffc4b03e40dfc393f761801d8fcd71 MD5 (bits23.txt) = 0d91a89ac456e2414f4128a9efede831 MD5 (bits24.txt) = 7aadd1a7a642a14a1b9c1bd3db163c31 MD5 (bits25.txt) = eaaf57e41a9a05ee57133aa0be5f5797 MD5 (bits26.txt) = 065fb7744556ebde22b0294f81c17671 MD5 (bits27.txt) = 9c2183dbda98ea3ce2c3a37e878c559d MD5 (bits28.txt) = 5741520392ba77db7ede5c08f2726491 MD5 (bits29.txt) = efebba84fa7466ff2c7531857ae1e994 MD5 (bits30.txt) = fa4fc3e046aa554ec096d9bf9254f057 MD5 (bits31.txt) = 0d0209a42c8e66162fa5fba081665242 MD5 (bits32.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits33.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits34.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits35.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits36.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits37.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits38.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits39.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits40.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits41.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits42.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits43.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits44.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits45.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits46.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits47.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits48.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits49.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits50.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits51.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits52.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits53.txt) = 5bbbc2a86812ec919111b11ef77653c1 MD5 (bits54.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits55.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits56.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits57.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits58.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits59.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits60.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits61.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits62.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits63.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (bits64.txt) = 6647528ca64beb8e6e8248f9d45e531d MD5 (single2147483646.txt) = a3b168c43bbbe199bc2d95ac4c328bd5 -- 2^31 - 2 MD5 (single2147483647.txt) = 0d0209a42c8e66162fa5fba081665242 -- 2^31 - 1 MD5 (single2147483648.txt) = 7bca1bfe12c7f47d7083f9a8fda5bb10 -- 2^31 MD5 (single2147483649.txt) = a9bf69b4cb6daf10690067422efcc318 -- 2^31 + 1 MD5 (single2147483650.txt) = b7d270c5f592416a8c4477878424deb1 -- 2^31 + 2 MD5 (single4294967294.txt) = 5bbbc2a86812ec919111b11ef77653c1 -- 2^32 - 2 MD5 (single4294967295.txt) = 5bbbc2a86812ec919111b11ef77653c1 -- 2^32 - 1 MD5 (single4294967296.txt) = 6647528ca64beb8e6e8248f9d45e531d -- 2^32 MD5 (single4294967297.txt) = fc2504bd79ec05192cfc5cdda15cc7a4 -- 2^32 + 1 MD5 (single8589934590.txt) = 5bbbc2a86812ec919111b11ef77653c1 -- 2^33 - 2 MD5 (single8589934591.txt) = 5bbbc2a86812ec919111b11ef77653c1 -- 2^33 - 1 MD5 (single8589934592.txt) = 6647528ca64beb8e6e8248f9d45e531d -- 2^33 MD5 (single8589934593.txt) = fc2504bd79ec05192cfc5cdda15cc7a4 -- 2^33 + 1