package bignum

Release v0.16.0

• Big_int

  • Adds stable_witness derivation to both the BigInt.Stable.V1 and BigInt.Stable.V2 modules. This facilitates compatibility checks between different versions of serialized data

• Big_num

  • Add deriving attributes:

    • Bignum.t, Bignum.Stable.t, and Bignum.Unstable.t derive sexp_grammar

  • Add new functions to Bignum:

    • truncate: Rounds the input towards zero to an integer
    • is_infinite: Returns true if the number is either positive or negative infinity
    • is_positive_infinity: Returns true if the number is positive infinity
    • is_negative_infinity: Returns true if the number is negative infinity
  • Add arg_type to Bignum, for ease of use in Command.t based parsers

Old pre-v0.15 changelogs (very likely stale and incomplete)

113.33.00

• This release improves the slow path of bignum of string. The previous version used a split on '_' followed by a concat, which allocated a bunch of intermediate strings.

113.24.00

• Switched to PPX.
• The library used polymorphic compare, rather than Zarith.Q's compare, in a few locations. Fixed this.
• Previously stable types in Bignum were defined with unstable types in the scope. Fixd this.
• Update to zarith-1.4

• Bignum.of_string needs to handle different formats for its input. The previous version of the code was trying to parse the common format (floats), and in case of failure, was attempting to use a different format (based on the error). This resulted in the string being parsed twice in some cases.

  This version is a complete rewriting of of_string to do the parsing in one step. The new code for to_string encode an automaton and remembers the positions of the various elements of the string (depending on the format).

  This feature uses a function which has been upstreamed in the new version of ZArith (1.4) which is a variant of the Zarith.of_string function to work with substrings. This variant alone is responsible for a big part of the performance improvement.

  The new version of the code performs better than the original one in all cases. The performance improvement are variable depending on the micro benchmark. See below.

  We also tried to implement the lexing engine using OCamllex. This makes for a much more concise description, but the performance are significantly lower. OCamllex produces code which allocates some table and some state, which is avoided in the hand written code. Also, it will allocate the sub strings matched.

  New version (patch for ZArith + of_substring, reimplementation of of_string)

  ┌─────────────────────────────────────────────────────────────────────┬──────────────┬───────────┬──────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├─────────────────────────────────────────────────────────────────────┼──────────────┼───────────┼──────────┼──────────┼────────────┤ │ bigint\_bench.ml random │ 48_381.13ns │ 7_166.00w │ 1.24w │ 1.24w │ 45.12% │ │ bigint\_bench.ml:vs. Big\_int plus_self │ 293.96ns │ 72.00w │ │ │ 0.27% │ │ bigint\_bench.ml:vs. Big\_int plus_other │ 807.62ns │ 124.00w │ │ │ 0.75% │ │ bigint\_bench.ml:vs. Big\_int mult_self │ 353.98ns │ 91.00w │ │ │ 0.33% │ │ bigint\_bench.ml:vs. Big\_int mult_other │ 783.78ns │ 128.00w │ │ │ 0.73% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (decimal) │ 14_415.44ns │ 475.00w │ │ │ 13.44% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (scientific) │ 61_363.80ns │ 3_929.00w │ │ │ 57.23% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (fraction) │ 24_957.02ns │ 303.00w │ │ │ 23.28% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (decimal) │ 15_867.52ns │ 1_523.00w │ │ │ 14.80% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (scientific) │ 33_345.31ns │ 4_206.00w │ │ │ 31.10% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (fraction) │ 31_770.26ns │ 3_779.00w │ │ │ 29.63% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (decimal) │ 9_726.82ns │ 380.00w │ │ │ 9.07% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (scientific) │ 28_141.40ns │ 2_059.00w │ │ │ 26.25% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (fraction) │ 70_436.16ns │ 5_541.00w │ │ │ 65.69% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (decimal) │ 27_000.73ns │ 1_994.00w │ │ │ 25.18% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (scientific) │ 66_057.63ns │ 6_217.00w │ │ │ 61.61% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (fraction) │ 107_219.89ns │ 8_097.00w │ │ │ 100.00% │ │ bignum\_bench.ml:Bignum binprot roundtrip compact │ 5_997.81ns │ 581.00w │ │ │ 5.59% │ │ bignum\_bench.ml:Bignum binprot roundtrip classic │ 18_522.20ns │ 779.00w │ │ │ 17.27% │ │ bignum\_bench.ml:round round_decimal:0 │ 8_479.49ns │ 463.00w │ │ │ 7.91% │ │ bignum\_bench.ml:round round_decimal:3 │ 24_621.71ns │ 2_115.00w │ │ │ 22.96% │ │ bignum\_bench.ml:round round_decimal:6 │ 26_896.35ns │ 2_437.00w │ │ │ 25.09% │ │ bignum\_bench.ml:round round_decimal:9 │ 29_428.19ns │ 2_730.00w │ │ │ 27.45% │ │ bignum\_bench.ml:round round │ 8_452.31ns │ 459.00w │ │ │ 7.88% │ └─────────────────────────────────────────────────────────────────────┴──────────────┴───────────┴──────────┴──────────┴────────────┘

  Original version

  ┌─────────────────────────────────────────────────────────────────────┬──────────────┬───────────┬──────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├─────────────────────────────────────────────────────────────────────┼──────────────┼───────────┼──────────┼──────────┼────────────┤ │ bigint\_bench.ml random │ 51_218.04ns │ 7_166.00w │ 1.25w │ 1.25w │ 43.26% │ │ bigint\_bench.ml:vs. Big\_int plus_self │ 336.84ns │ 72.00w │ │ │ 0.28% │ │ bigint\_bench.ml:vs. Big\_int plus_other │ 837.73ns │ 124.00w │ │ │ 0.71% │ │ bigint\_bench.ml:vs. Big\_int mult_self │ 411.03ns │ 91.00w │ │ │ 0.35% │ │ bigint\_bench.ml:vs. Big\_int mult_other │ 808.03ns │ 128.00w │ │ │ 0.68% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (decimal) │ 29_650.60ns │ 2_415.00w │ │ │ 25.04% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (scientific) │ 92_495.93ns │ 6_465.00w │ │ │ 78.12% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (fraction) │ 39_482.77ns │ 2_060.00w │ │ │ 33.35% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (decimal) │ 16_195.93ns │ 1_523.00w │ │ │ 13.68% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (scientific) │ 34_227.78ns │ 4_059.00w │ │ │ 28.91% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (fraction) │ 32_856.17ns │ 3_779.00w │ │ │ 27.75% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (decimal) │ 19_745.71ns │ 2_149.00w │ │ │ 16.68% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (scientific) │ 51_024.99ns │ 3_853.00w │ │ │ 43.09% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (fraction) │ 88_884.15ns │ 7_819.00w │ │ │ 75.07% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (decimal) │ 32_812.27ns │ 2_498.00w │ │ │ 27.71% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (scientific) │ 77_518.77ns │ 6_369.00w │ │ │ 65.47% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (fraction) │ 118_402.78ns │ 8_907.00w │ │ │ 100.00% │ │ bignum\_bench.ml:Bignum binprot roundtrip compact │ 8_947.02ns │ 371.00w │ │ │ 7.56% │ │ bignum\_bench.ml:Bignum binprot roundtrip classic │ 22_799.74ns │ 1_039.00w │ │ │ 19.26% │ │ bignum\_bench.ml:round round_decimal:0 │ 8_176.74ns │ 463.00w │ │ │ 6.91% │ │ bignum\_bench.ml:round round_decimal:3 │ 25_798.77ns │ 2_115.00w │ │ │ 21.79% │ │ bignum\_bench.ml:round round_decimal:6 │ 28_561.23ns │ 2_437.00w │ │ │ 24.12% │ │ bignum\_bench.ml:round round_decimal:9 │ 30_861.38ns │ 2_730.00w │ │ │ 26.06% │ │ bignum\_bench.ml:round round │ 8_237.26ns │ 459.00w │ │ │ 6.96% │ └─────────────────────────────────────────────────────────────────────┴──────────────┴───────────┴──────────┴──────────┴────────────┘

  Tentative version using OCamllex

  ┌─────────────────────────────────────────────────────────────────────┬──────────────┬────────────┬──────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├─────────────────────────────────────────────────────────────────────┼──────────────┼────────────┼──────────┼──────────┼────────────┤ │ bigint\_bench.ml random │ 48_164.21ns │ 7_166.00w │ 1.25w │ 1.25w │ 39.99% │ │ bigint\_bench.ml:vs. Big\_int plus_self │ 285.84ns │ 72.00w │ │ │ 0.24% │ │ bigint\_bench.ml:vs. Big\_int plus_other │ 768.12ns │ 124.00w │ │ │ 0.64% │ │ bigint\_bench.ml:vs. Big\_int mult_self │ 343.14ns │ 91.00w │ │ │ 0.28% │ │ bigint\_bench.ml:vs. Big\_int mult_other │ 780.00ns │ 128.00w │ │ │ 0.65% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (decimal) │ 26_931.12ns │ 3_108.00w │ │ │ 22.36% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (scientific) │ 79_750.28ns │ 6_599.00w │ 0.11w │ 0.11w │ 66.21% │ │ bignum\_bench.ml:Bignum of\_string/to\_string of_string (fraction) │ 34_988.94ns │ 4_300.00w │ │ │ 29.05% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (decimal) │ 15_958.17ns │ 1_523.00w │ │ │ 13.25% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (scientific) │ 32_495.25ns │ 4_059.00w │ │ │ 26.98% │ │ bignum\_bench.ml:Bignum of\_string/to\_string to_string (fraction) │ 31_802.75ns │ 3_779.00w │ │ │ 26.40% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (decimal) │ 18_742.81ns │ 2_924.00w │ │ │ 15.56% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (scientific) │ 45_282.09ns │ 4_622.00w │ │ │ 37.60% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp of_sexp (fraction) │ 86_907.83ns │ 8_777.00w │ 0.15w │ 0.15w │ 72.16% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (decimal) │ 35_727.73ns │ 4_493.00w │ │ │ 29.66% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (scientific) │ 82_247.61ns │ 8_273.00w │ 0.13w │ 0.13w │ 68.29% │ │ bignum\_bench.ml:Bignum of\_sexp/to\_sexp to_sexp (fraction) │ 120_445.25ns │ 10_688.00w │ 0.12w │ 0.12w │ 100.00% │ │ bignum\_bench.ml:Bignum binprot roundtrip compact │ 6_734.49ns │ 371.00w │ │ │ 5.59% │ │ bignum\_bench.ml:Bignum binprot roundtrip classic │ 21_773.79ns │ 1_890.00w │ │ │ 18.08% │ │ bignum\_bench.ml:round round_decimal:0 │ 8_306.45ns │ 463.00w │ │ │ 6.90% │ │ bignum\_bench.ml:round round_decimal:3 │ 24_714.96ns │ 2_115.00w │ │ │ 20.52% │ │ bignum\_bench.ml:round round_decimal:6 │ 26_894.27ns │ 2_437.00w │ │ │ 22.33% │ │ bignum\_bench.ml:round round_decimal:9 │ 29_343.81ns │ 2_730.00w │ │ │ 24.36% │ │ bignum\_bench.ml:round round │ 8_296.05ns │ 459.00w │ │ │ 6.89% │ └─────────────────────────────────────────────────────────────────────┴──────────────┴────────────┴──────────┴──────────┴────────────┘

113.00.00

• Fixed a bug in the =Zarith= library's to_float function.

  These fixes first introduce tests from the base distribution, and then backport a bugfix to the handling of to_float.

112.35.00

• Upgraded from Zarith 1.2 to 1.3.
• Removed dependence on Big_int.

112.24.00

• Fixed exception raised by Bignum.sexp_of_t when the denominator is zero.

112.17.00

• Added Bigint.random function, which produces a uniformly distributed value.

112.06.00

• Added functions to round from Bignum.t to Bigint.t, and to convert Bigint.t into Bignum.t.

112.01.00

• Added Bignum.Bigint module, with arbitrary-precision integers based on Zarith, which is significantly faster than the Num.Big_int library.

111.17.00

• Improved the performance of binprot deserialization by removing the allocation of an intermediate type.

111.13.00

• Eliminated the dependence of Bignum on Re2, and reduced dependence from Core to Core_kernel.
• Extended the rounding interface to bring it in line with int and float rounding.

• Improved the performance of Bignum's binprot.

  Bignum's binprot had been to just binprot the decimal string representation. This is both slow to do and unnecessarily big in the majority of cases. Did something better in the majority of cases and fell back to this representation in the exceptional case.

        $ ./inline_benchmarks_runner
  Estimated testing time 20s (2 benchmarks x 10s). Change using -quota SECS.

  Name	Time/Run	mWd/Run	Percentage
  bignum0.ml:Stable:Bignum binprot roundtrip compact	7.87us	490.00w	32.88%
  bignum0.ml:Stable:Bignum binprot roundtrip classic	23.94us	1_079.00w	100.00%