# UInt64 - 64-bit unsigned integer with division

**URL:** <https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942>\
**Category:** Show and Tell\
**Created:** [June 20, 2020, 11:06am UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942 "2020-06-20T11:06:05Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![malaire](https://avatars.discourse-cdn.com/v4/letter/m/b782af/32.png) [@malaire](https://discourse.elm-lang.org/u/malaire)\
**Post date:** [June 20, 2020, 11:06am UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/1 "2020-06-20T11:06:05Z")

</div>

I’ve just published new package [malaire/elm-uint64](https://package.elm-lang.org/packages/malaire/elm-uint64/latest/) - 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:

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

```

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

```auto
-- `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:

```nohighlight
                                      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.

---

<div class="post-metadata">

**Author:** ![MartinS](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/martins/32/3137_2.png) [@MartinS](https://discourse.elm-lang.org/u/MartinS)\
**Post date:** [June 20, 2020, 11:53am UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/2 "2020-06-20T11:53:59Z")

</div>

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](https://package.elm-lang.org/packages/folkertdev/elm-int64/latest/Int64) but it lacks a `fromString` function)

---

<div class="post-metadata">

**Author:** ![malaire](https://avatars.discourse-cdn.com/v4/letter/m/b782af/32.png) [@malaire](https://discourse.elm-lang.org/u/malaire)\
**Post date:** [June 20, 2020, 11:57am UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/3 "2020-06-20T11:57:55Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![MartinS](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/martins/32/3137_2.png) [@MartinS](https://discourse.elm-lang.org/u/MartinS)\
**Post date:** [June 20, 2020, 12:01pm UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/4 "2020-06-20T12:01:45Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![rupert](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rupert/32/1775_2.png) [@rupert](https://discourse.elm-lang.org/u/rupert)\
**Post date:** [June 20, 2020, 12:27pm UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/5 "2020-06-20T12:27:21Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![malaire](https://avatars.discourse-cdn.com/v4/letter/m/b782af/32.png) [@malaire](https://discourse.elm-lang.org/u/malaire)\
**Post date:** [June 20, 2020, 9:29pm UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/6 "2020-06-20T21:29:21Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![MartinS](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/martins/32/3137_2.png) [@MartinS](https://discourse.elm-lang.org/u/MartinS)\
**Post date:** [June 21, 2020, 7:16am UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/7 "2020-06-21T07:16:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![wondible](https://avatars.discourse-cdn.com/v4/letter/w/e9c0ed/32.png) [@wondible](https://discourse.elm-lang.org/u/wondible)\
**Post date:** [June 21, 2020, 12:41pm UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/8 "2020-06-21T12:41:03Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![malaire](https://avatars.discourse-cdn.com/v4/letter/m/b782af/32.png) [@malaire](https://discourse.elm-lang.org/u/malaire)\
**Post date:** [June 21, 2020, 1:21pm UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/9 "2020-06-21T13:21:40Z")

</div>

Mersenne twister would certainly be an interesting benchmark for `UInt64`.

Looking at [pseudo code](https://en.wikipedia.org/wiki/Mersenne_Twister#Pseudocode), 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.

---

<div class="post-metadata">

**Author:** ![miniBill](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/minibill/32/800_2.png) [@miniBill](https://discourse.elm-lang.org/u/miniBill)\
**Post date:** [June 21, 2020, 4:05pm UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/10 "2020-06-21T16:05:23Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![malaire](https://avatars.discourse-cdn.com/v4/letter/m/b782af/32.png) [@malaire](https://discourse.elm-lang.org/u/malaire)\
**Post date:** [June 22, 2020, 4:39pm UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/11 "2020-06-22T16:39:17Z")

</div>

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](https://github.com/malaire/elm-uint64/tree/master/examples/MersenneTwister)

Quick benchmark:

```nohighlight
                        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.

---

<div class="post-metadata">

**Author:** ![wondible](https://avatars.discourse-cdn.com/v4/letter/w/e9c0ed/32.png) [@wondible](https://discourse.elm-lang.org/u/wondible)\
**Post date:** [June 25, 2020, 12:49pm UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/12 "2020-06-25T12:49:02Z")

</div>

> [@malaire](#):
>
> I was interested to know how fast this is, so I added Mersenne Twister as first example.

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.

---

<div class="post-metadata">

**Author:** ![malaire](https://avatars.discourse-cdn.com/v4/letter/m/b782af/32.png) [@malaire](https://discourse.elm-lang.org/u/malaire)\
**Post date:** [June 25, 2020, 1:23pm UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/13 "2020-06-25T13:23:18Z")

</div>

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](https://gcc.gnu.org/onlinedocs/libstdc%2B%2B/latest-doxygen/a01537.html#ga9606c7ecfbdedbd7ee5d8b908f4e2275), it does use the same variant I used here.

---

<div class="post-metadata">

**Author:** ![malaire](https://avatars.discourse-cdn.com/v4/letter/m/b782af/32.png) [@malaire](https://discourse.elm-lang.org/u/malaire)\
**Post date:** [June 27, 2020, 8:17am UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/14 "2020-06-27T08:17:25Z")

</div>

# 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`).

---

<div class="post-metadata">

**Author:** ![system](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/1X/50a05e53677a2c3b47776d7abd0f113eb50193a1.png) [@system](https://discourse.elm-lang.org/u/system)\
**Post date:** [July 7, 2020, 8:17am UTC](https://discourse.elm-lang.org/t/uint64-64-bit-unsigned-integer-with-division/5942/15 "2020-07-07T08:17:27Z")

</div>

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