UInt64 - 64-bit unsigned integer with division

Show and Tell
1

I’ve just published new package malaire/elm-uint64 - 64-bit unsigned integer using wrapping overflow.

Some functions and optimizations are still missing, but enough is implemented to publish first version.

Includes for example bitwise functions like shifts and rotations:

UInt64.fromInt32s 0x11223344 0xAABBCCDD
    |> UInt64.rotateRightBy 20
    |> UInt64.toHexString
    --> "BCCDD11223344AAB"

And math functions like subtraction, division with modulo, and exponentiation:

-- `0 - 0xFF` wraps around to `0xFFFFFFFFFFFFFF01`
UInt64.sub UInt64.zero (UInt64.fromInt 0xFF)
    |> UInt64.toHexString
    --> "FFFFFFFFFFFFFF01"

-- ( 0xFFFFFFFFFFFFFFFF / 1e10, 0xFFFFFFFFFFFFFFFF % 1e10 )
UInt64.divMod UInt64.maxValue (UInt64.floor 1e10)
    |> Tuple.mapBoth UInt64.toFloat UInt64.toFloat
    --> ( 1844674407, 3709551615 )

-- `(3 ^ 10000000000000000000) % 2^64`
UInt64.pow (UInt64.fromInt 10) (UInt64.fromInt 19)
    |> UInt64.pow (UInt64.fromInt 3)
    |> UInt64.toString
    --> "12038004833498693633"

Performance

Some quick benchmark results. As usual I’m not interested in proper benchmarking, so take these with 2^64 grains of salt:

                                      runs / second
pow   : 64-bit number ^ 64-bit number: ~     40 000
pow   : 64-bit number ^ 251          : ~    300 000
divMod: 64-bit number / 40-bit number: ~  2 000 000
pow   : 64-bit number ^ 16           : ~  3 000 000
divMod: 64-bit number / 29-bit number: ~  5 000 000
add, sub, mul                        : > 10 000 000
bitwise shift/rotate by 1 bit        : ~ 20 000 000

Benchmarking was done with elm make --optimize, Firefox 68, Debian Linux and Core i5 3570K 3.4 GHz.

Testing

Every function is tested with at least one full-range fuzz test.

10 Likes
2

Cool package!

I’ve been working on a wrapper for the Discord HTTP API. A lot of the IDs they use are uint64. It looks like this package should let me stop treating those IDs as strings and instead get some more type safety by converting them to uint64. (I know there’s folkertdev/int64 but it lacks a fromString function)

3

Currently fromString is missing from this package also, but it’s on my todo list. Simple implementation could be to just split string to two parts, use String.toInt on each, and combine results with multiplication.

4

Oh whoops, sorry about that. I think I glanced at the documentation, saw UInt64.toString and UInt64.fromInt and mixed the two together.

5

Awesome package. I mentioned previously I have a few places I need to do 64-bit math, simply because some back-end endpoint outside of my control can give 64-bit values - this is really helpful.

6

I just added fromString to master. I’m thinking of making next release in about a week, unless someone wants earlier release.

4 Likes
7

Awesome, thanks! I don’t need a fromString function immediately so release the next version at your leisure.

8

Interesting. I have an application where I’d like a bit-identical std::mt19937_64, and while I had not looked seriously at the implementation options, I hadn’t’ considered there might be some pieces available. At this point it seems like my options are either implement myself in JS or Elm, or make a small server to run the C++ code.

9

Mersenne twister would certainly be an interesting benchmark for UInt64.

Looking at pseudo code, it would use and, xor, leftShiftBy, rightShiftZfBy, mul and modulo with 312 for 64-bit version.

These all are implemented for UInt64, if using divMod for modulo. Modulo can be made faster by implementing it separately from divMod, but I havn’t done that yet as I’m still considering use cases and how to implement div/mod without too much code duplication or overhead from function calls.

Basically I’m considering whether to duplicate code of divMod three times in divMod/div/mod, removing unneeded pieces from div and mod to make them faster for small values. (Each would still call divModFast if needed, so for large values there would be no difference in speed.)

EDIT: Actually Mersenne twister uses that modBy 312 only with small numbers, so it doesn’t use 64-bit modulo.

10

My two cents: code duplication is not bad in this case, because it’s “immutable” code, so the usual downsides of duplication don’t apply.

11

I was interested to know how fast this is, so I added Mersenne Twister as first example.

Code: https://github.com/malaire/elm-uint64/tree/master/examples/MersenneTwister

Quick benchmark:

                        runs / second
initByArray                       800
uint64 (with twist)             2 000
init                            8 000
uint64 (without twist)      1 400 000

p.s. Those foldl:s should probably be replaced with something faster, e.g. recursive tail calls.

1 Like
12

This is amazing thank you.

Sadly it doesn’t seem to be a perfect emulation of the g++ twister out of the box, so I’ll still need to figure out how to get that bit of code out of stdlib into a development environment where I can look at intermediate values in order to see where they diverge.

13

I’ve read that there are different variants of mt19937_64, but here I just used the variant which matches original C code, to make verifying simpler.

According to libstdc++ docs, it does use the same variant I used here.

14

1.1.0

Version 1.1.0 has just been published.

Main features are

  • fromString which converts decimal/hex/octal/binary String to UInt64 and
  • many internal optimizations, which have increased speed of nearly all functions.

div and mod were also added along with some smaller functions (isEven, isOdd, isZero, shiftRightZfBy1, square).

7 Likes
15

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.