Unleashed Pascal (async/await, parallel for, match, string interpolation & more)

[MathMan]

good day Fibonacci 
I just tried FPC unleashed with a pet project and the performance increased 75% 
Q: when installing a new version, do I uninstall the previous version ?

Good day to you too

But... how? Unleashed is mostly about new language features rather than performance. My guess is that you were using the latest stable release (FPC 3.2.2), which is over 5 years old, and switching to the current trunk-based compiler got you all the optimizations that have accumulated since then. Or did you make use of any of the threading features (parallel for, futures)?

As for installing: there's no need to uninstall the previous version. Just run the installer again and point it to the existing installation directory. The "Install" button will automatically change to "Update", preserving your configuration.

Educated guess - native support for UInt128

[Fibonacci]

@MathMan: Perfect timing - I need you!


BigInts - arbitrary precision integers, decimals and rationals

Over the years I've seen a few different takes on big numbers on this forum. Whenever I actually needed big integers I reached for @benibela's Big Decimal Math - a fine library, but it's a BigDecimal at heart: for pure integer work it was never the complete tool (no bitwise, no primes or modular arithmetic). So I wrote my own: BigInts.

A single self-contained unit, nothing behind it but the RTL. Four value types:

• BigInt - signed; bitwise ops use two's complement with infinite sign extension
• UBigInt - unsigned; anything that would drop below zero raises ERangeError
• BigDecimal - decimal float on the same core: a BigInt mantissa times a power of ten; exact + - *, division and roots at any precision
• BigRational - exact fraction: a normalized num/den pair, so 1/3 stays 1/3 and never rounds

No size limit whatsoever - RAM is the only ceiling.

The idea for the integer types is: everything a plain integer can do, with no "buts". The full operator set, bitwise included: + - * div mod / ** shl shr and or xor not, all comparisons, inc/dec, compound assignments, mixed freely with plain integers and strings on either side. Literals of any size in any base 2..36, with _ separators and $ 0x % 0b & 0o prefixes. Conversions to and from every native width - including Int128/UInt128 where the compiler provides the native type (Unleashed does).

On top of that sits a big number-theory and combinatorics layer: Montgomery modPow (plus a side-channel-resistant variant and a reusable TModRing context), modInverse, modSqrt, sqrtModN, nthRootMod, crt, discreteLog, multiplicativeOrder/primitiveRoot, binomialMod, lucasSequence, Baillie-PSW isPrime and Miller-Rabin, randomPrime/randomSafePrime, Pollard-Brent factorize with eulerPhi/moebius/divisors on top, exact primePi, continued fractions, factorial/fibonacci/binomial/bernoulli/partitions and friends. There's a pluggable random suite (xoshiro256**, PCG64, OS entropy; per-thread, no locks) plus constant-time helpers (equalsCT/compareCT, secureClear, randomSecure) for the crypto-adjacent code.

The BigDecimal layer does exact decimal arithmetic (0.1 + 0.2 = 0.3, money never drifts), six rounding modes, shortest/exact float conversions both ways, and a full analytic toolbox at any precision - pi, exp, ln, fractional powers, trig, hyperbolics, gamma, erf. And since everything was already there, it also got calc: a whole expression evaluator in one call - operators with proper precedence, all the functions above, pi/e/tau/phi constants, at whatever precision you ask for.

Code: Pascal  [Select][+][-]

1. program bigdemo;
2.  
3. {$mode unleashed}
4.  
5. uses BigInts;
6.  
7. begin
8.   // integers
9.   var a: BigInt := '123456789012345678901234567890';
10.   var b: BigInt := '-0xDEAD_BEEF';
11.   writeln($'a * b = {a * b}');                            // -461225743873659625387365962538275370510
12.   writeln($'2**4096 has {(BigInt(2) ** 4096).digitCount} digits');
13.   var (q, r) := a.divMod(b);
14.   writeln($'{q} rem {r}');                                // -33045810984509695732 rem 3655357702
15.   writeln($'prime? {UBigInt.randomPrime(256).isPrime}');  // TRUE
16.  
17.   // decimals - same core
18.   writeln($'{BigDecimal('0.1') + BigDecimal('0.2')}');    // 0.3, exactly
19.   writeln($'{BigDecimal(2).sqrt(30)}');                   // 1.41421356237309504880168872421
20.   writeln($'{BigDecimal.pi(50)}');                        // 3.14159265358979323846264338327950288419716939937511
21.   writeln($'{BigDecimal.calc('(1 + sqrt(5)) / 2', 50)}'); // 1.61803398874989484820458683436563811772030917980576
22.  
23.   // exact fractions - never rounds
24.   writeln($'1/3 + 1/6 = {BigRational.create(1,3) + BigRational.create(1,6)}');  // 1/2
25.   var approx: BigRational := '355/113';
26.   writeln($'{approx} ~= {Double(approx)}');               // 355/113 ~= 3.14159...
27.   readln;
28. end.

Speed - the full picture. Both sides -O3, time per operation, one x64 desktop, results cross-checked for correctness before timing. Integers against GMP 6.3.0; decimals against @benibela's bigdecimalmath, since that's the reference point here.

Against GMP - the gold standard, decades of hand-scheduled assembly, FFT and sub-quadratic algorithms I don't implement - the integer core sits at ~1.4-3.5x on the bulk, up to ~4.9x on the tightest small cases (a short add, gcd), and actually edges ahead on unbalanced multiply. For a single Pascal unit I'll take it.

On decimals the split is clean, and honestly a bit brutal. Base-10 BCD wins where it's naturally strong - parse, format, small adds. But everything that actually costs - multiply, divide, division at precision, powers, roots - BigInts takes by one to three orders of magnitude, and the gap only widens with size. sqrt to 50 digits of a 1000-digit value: 15 us here, 38 ms there. Same operation.

Code: Text  [Select][+][-]

1. operation                     BigInts            GMP   ratio       BeniBela   ratio
2. (ratio = BigInts / competitor;  >1 slower,  <1 faster,  - = unsupported)
3. -- integers (BigInts vs GMP 6.3.0)
4. add 128b                     0.016 us       0.005 us    2.9x              -       -
5. add 1024b                    0.037 us       0.008 us    4.9x              -       -
6. add 262144b                  1.721 us       1.258 us    1.4x              -       -
7. sub 1024b                    0.038 us       0.008 us    4.5x              -       -
8. sub 262144b                  1.648 us       1.297 us    1.3x              -       -
9. mul 128b                     0.020 us       0.006 us    3.2x              -       -
10. mul 1024b                    0.187 us       0.132 us    1.4x              -       -
11. mul 8192b                    6.284 us       4.178 us    1.5x              -       -
12. mul 65536b                 184.202 us      84.158 us    2.2x              -       -
13. mul 65536x1024b              7.063 us       8.664 us    0.8x              -       -
14. div 2048/1024b               0.370 us       0.207 us    1.8x              -       -
15. div 131072/65536b          716.928 us     176.492 us    4.1x              -       -
16. sqr 8192b                    5.522 us       2.592 us    2.1x              -       -
17. sqr 65536b                 168.743 us      56.059 us    3.0x              -       -
18. divmod 131072/65536b       714.803 us     207.093 us    3.5x              -       -
19. toString 65536b            422.740 us     224.807 us    1.9x              -       -
20. parse 65536b               244.718 us     137.774 us    1.8x              -       -
21. modPow 1024b               435.148 us     258.117 us    1.7x              -       -
22. modPow 2048b              2783.518 us    1968.972 us    1.4x              -       -
23. gcd 1024b                   10.998 us       2.690 us    4.1x              -       -
24. gcd 16384b                 420.693 us     115.190 us    3.7x              -       -
25. -- decimals at 100 digits (BigInts vs BeniBela)
26. parse                        1.077 us              -       -       0.624 us   1.72x
27. toString                     1.159 us              -       -       0.353 us   3.29x
28. add                          0.130 us              -       -       0.086 us   1.51x
29. mul                          0.327 us              -       -       0.999 us   0.33x
30. div (integer)                0.653 us              -       -       8.107 us   0.08x
31. divide prec 50               0.317 us              -       -      31.450 us   0.01x
32. pow ^7                       1.758 us              -       -      45.633 us   0.04x
33. sqrt prec 50                 2.975 us              -       -    1057.378 us   0.00x
34. -- decimals at 1000 digits (BigInts vs BeniBela)
35. parse                       10.437 us              -       -       6.008 us   1.74x
36. toString                    16.011 us              -       -       3.090 us   5.18x
37. add                          0.677 us              -       -       0.379 us   1.79x
38. mul                          2.386 us              -       -      66.554 us   0.04x
39. div (integer)                2.996 us              -       -     481.573 us   0.01x
40. divide prec 50               4.535 us              -       -    1907.978 us   0.00x
41. pow ^7                      67.512 us              -       -    4118.609 us   0.02x
42. sqrt prec 50                15.423 us              -       -   37704.275 us   0.00x
43. -- analytic (BigInts only)
44. operation                 100 digits      1000 digits
45. pi                           0.668 us         1.484 us
46. exp                         38.287 us      1134.620 us
47. ln                          32.335 us       670.304 us
48. sin                         27.515 us      1078.874 us
49. nthRoot ^7                  14.907 us       473.286 us
50. pow (fractional)            58.864 us      1699.330 us

The integer core carries a bit of assembler (x86_64 and i386 inner loops behind a USEASM define), with a pure-Pascal fallback for every other target. Small values up to 256 bits live inline in the value with no heap allocation at all.

One more angle - BigInt vs BeniBela on integers. Since bigdecimalmath can hold big integers too, here's BigInt against it on integer operands, across sizes. Arithmetic is 2-500x faster and the gap widens with size; BeniBela wins parse and format, where base-10 BCD is trivially decimal - that's the honest trade.

Code: Text  [Select][+][-]

1. operation   digits          BigInt        BeniBela      ratio
2. add            100        0.060 us        0.102 us     0.594x
3. add           1000        0.075 us        0.302 us     0.247x
4. add          10000        0.263 us        2.380 us     0.110x
5. add         100000        1.988 us       23.023 us     0.086x
6. add        1000000       21.703 us      580.950 us     0.037x
7. sub            100        0.052 us        0.100 us     0.518x
8. sub           1000        0.065 us        0.246 us     0.266x
9. sub          10000        0.248 us        2.022 us     0.123x
10. sub         100000        2.004 us       19.761 us     0.101x
11. sub        1000000       19.437 us      536.455 us     0.036x
12. mul            100        0.087 us        0.543 us     0.159x
13. mul           1000        1.280 us       27.658 us     0.046x
14. mul          10000       64.479 us     2641.059 us     0.024x
15. mul         100000     2077.511 us   257024.800 us     0.008x
16. div            100        0.096 us        4.527 us     0.021x
17. div           1000        0.926 us      237.538 us     0.004x
18. div          10000       50.458 us    21045.512 us     0.002x
19. parse          100        0.568 us        0.322 us     1.765x
20. parse         1000        4.797 us        2.858 us     1.679x
21. parse        10000       89.771 us       28.981 us     3.098x
22. parse       100000     2765.787 us      278.385 us     9.935x
23. parse      1000000    82324.375 us     2875.304 us    28.632x
24. toString       100        0.571 us        0.201 us     2.846x
25. toString      1000        7.142 us        1.600 us     4.464x
26. toString     10000      155.225 us       15.314 us    10.136x
27. toString    100000     5581.614 us      153.642 us    36.329x
28. toString   1000000   164455.200 us     1580.764 us   104.035x

The ask. I'm no mathematician, so I'd really like someone who is - or anyone already doing real work with big numbers - to put this through its paces: the algorithms, the correctness, the corner cases. The self-test passes 99k+ assertions, but a test suite only means the code is consistent with itself. The catch: you need a compiler that understands {$mode unleashed} to use it.

Which is also why it's posted here, in the Unleashed thread rather than as its own topic: BigInts is Unleashed-only - it will not build under objfpc. The library relies heavily on inline variables, tuples (divMod, gcdExt, and factorize all return them, while bernoulli returns an exact (num, den) pair that drops straight into a BigRational - rather clumsy without tuples), statement expressions, and string interpolation. That's the beauty of Unleashed for me: features like these cut the boilerplate, allowing a unit this large to come together faster while remaining easy to maintain.

Repo, README and examples: https://github.com/fibodevy/BigInts

[Thaddy]

I am not really a @mathman <sic> either, just proficient, but you can compare results with the late Rudy Velthuis bigxxx units and these are verified to be correct. Luck has it that is website is still active, many years after he passed away too soon:
https://github.com/rvelthuis/DelphiBigNumbers
http://www.rvelthuis.de/programs/index.html
http://www.rvelthuis.de/programs/bigintegers.html

I considered him a true friend and we collaborated in Delphi <--> C++ interfacing.
RIP Rudy.(2019-05-13) Brillant programmer.

You might pick up some ideas from his implementation. It compiles with fpc build for name spaces. (or parse the unit clauses)

For you it is likely you only need to read the sourcecode.

[Fibonacci]

@Thaddy: thank you - great pointer, and a lovely tribute. A verified-correct reference is exactly what I want for cross-checking the core arithmetic, so I'll wire Velthuis's BigInteger into the test harness as an oracle.

Two notes.

First - good to know it builds under FPC in namespaces mode; thanks, that's easier than I'd assumed. It's still a whole set of units (BigIntegers, BigDecimals, BigRationals, a separate Primes unit, RandomNumbers, ...) rather than one file, but for oracle use you're right that reading the source is mostly all I need.

Second, on the crypto side: I ask because I'm building a small portable, no-install PGP tool, roughly in the spirit of gpg4usb (I really dislike Kleopatra). One key difference: gpg4usb still shells out to an external gpg.exe, whereas mine is completely standalone - built on bigints.pas, doing RSA key generation, encryption and decryption itself, and it works nicely. gpg4usb is my reference point; the one thing it's missing that I actually want is aliasing keys by a name I choose - people often don't put anything meaningful in the name/email fields, so keys get hard to tell apart, and a local alias would fix that.

So safety matters here, and that's the lens I looked at Velthuis through. It's a fine general-purpose bignum library, but it wasn't built as a crypto toolkit: primality is plain Miller-Rabin (deterministic only below ~3.4e14), no safe- or strong-prime generation, no constant-time modular exponentiation, and RandomProbablePrime draws from an LCG seeded off the wall clock - fine for testing, not for real keys.

Beyond the crypto bits, there's also a fair amount my code leans on that I don't see in Velthuis (unless I'm just not seeing it):

• crypto: modPowSec (constant-time), equalsCT/compareCT, secureClear, randomSecure* (OS entropy), TModRing
• primes: Baillie-PSW isPrime, randomSafePrime/randomStrongPrime, exact primePi/primeCount
• number theory: gcdExt, jacobi, kronecker, sqrtModN, nthRootMod, discreteLog, multiplicativeOrder/primitiveRoot, crt, eulerPhi, carmichaelLambda, moebius, sigma/tau/divisors/radical, factorize, continuedFraction
• combinatorics: factorial, fibonacci, lucas, binomial, multinomial, catalan, bell, stirling1/stirling2, bernoulli, partitions, subfactorial, primorial
• decimal analytic: pi, exp, ln, trig, hyperbolics, gamma, erf, agm, plus a calc expression evaluator
• other: an unsigned UBigInt type, toRoman/toWords, Int128/UInt128 conversions

None of that is a knock on Rudy's work - it's a rock-solid general-purpose library, just a different scope. That's exactly why BigInts grew its own layer, and why I keep the key-generation primitives in-house.

And honestly, I'm too lazy to write up a proper head-to-head until I actually hit my first bug in BigInts - that'll be the trigger. Until then, Velthuis stays a correctness oracle for the arithmetic.

[MathMan]

@Fibonacci

I will take a look. But the task you ask is hughe, so not sure yet if I can/want delve into this fully (throwing an anchor here).

Some things I can immediately state

- GMP is not the fastest FOSS implementation since some time now. Recently a lot of work has gone into the arithmetics in FLINT which has surpassed GMP. But comparing with GMP is still solid.
- You only tested "small" numbers. If, as you say, you sticked to schoolbook algorithms - GMP (and others) will run rings around you once you enter the range of million/billion digit numbers. So think about your use case carefully. The operator overloading approach may make this a suitable tool for rapid algorithm prototyping.
- you can not have a side-channel-resistant Montgomery modPow if you don't have side-channel-resistant add/sub/mul <= do you?

It'll take some time to go through such a hughe lib, so pls bear with me. I'll keep you posted on progress (or if I prefer/have to decline due to time constraints).

[Fibonacci]

you can not have a side-channel-resistant Montgomery modPow if you don't have side-channel-resistant add/sub/mul <= do you?

You're right - I don't, and thanks for pinning it down.

modPowSec runs a Montgomery ladder, so the sequence of operations no longer depends on the exponent bits. That kills the classic square-and-multiply leak on the exponent, and that's the whole scope of the Sec suffix. But it calls the ordinary schoolbook * and mod, which are variable-time (length normalization, division branches, no fixed-width limbs). So intermediate values still leak through timing even though the exponent pattern doesn't - it is not a constant-time bignum, and shouldn't be sold as one.

The only primitives I'd stand behind as constant-time are the secret-comparison helpers (equalsCT / compareCT) and secureClear. The library targets general-purpose bignum and prototyping, not hardened crypto.

It's a fresh lib, so this all gets fixed: I'll tone down that "side-channel resistant" comment to say exactly what it does, and a genuinely constant-time path (fixed-width limbs, branchless conditional subtract, no early exits) is on the list. Good catch.

And no rush at all - if you're short on time or would rather not dig into a lib this size, I completely understand, no problem either way. Any look you do give it is already appreciated.

[Thaddy]

Constant time requires that short-cut Boolean evaluation is OFF explicitly.
Which is a bit contradictory to the switch {$B+} // Off. Full evaluation
Will evaluate. 
https://www.freepascal.org/docs-html/current/prog/progsu4.html#x11-100001.2.4

Some standard units that contain procedures that rely on constant time are compiled with that after I had a discussion with Jonas many moons ago.

[Fibonacci]

@Thaddy:

Wiring Velthuis's BigInteger in as the correctness oracle, the first thing I hit is a bug in Velthuis.BigIntegers.Primes.pas line 204.

Ran it in a Delphi VM.

Code: Pascal  [Select][+][-]

1. program app;
2.  
3. uses Velthuis.BigIntegers, Velthuis.BigIntegers.Primes;
4.  
5. procedure main;
6. var
7.   n, p: BigInteger;
8. begin
9.   n := 14;
10.   p := NextProbablePrime(n, 20);
11.   writeln('N        = ', n.ToString);
12.   writeln('expected = 17');
13.   writeln('actual   = ', p.ToString);
14.   if p = n then
15.     writeln('>> BUG: returned N unchanged')
16.   else
17.     writeln('OK');
18. end;
19.  
20. begin
21.   main;
22.   readln;
23. end.

Output:

Code: Text  [Select][+][-]

1. N        = 14
2. expected = 17
3. actual   = 14
4. >> BUG: returned N unchanged

Fix: remove the last line (Result := N).

these are verified to be correct

Not really

So much for using it as a correctness oracle - if a "verified" reference ships a function that never works, I can't trust it to validate mine without first validating the oracle, which rather defeats the point.

[Thaddy]

I must have fixed that myself, then. Here my copy works. Sorry about that.
Strange, because it is mainstream Delphi goto....

[srvaldez]

@Fibonacci

I get the following errors when trying to compile bigints.pas

bigints.pas(2669,28) Error: Identifier not found "_"
bigints.pas(3644,18) Error: Illegal expression
bigints.pas(3644,22) Fatal: Syntax error, ")" expected but "identifier Q" found
Fatal: Compilation aborted


never mind, I was not using the main branch
sorry

[MathMan]

@fibonacci

I have taken some time to look through the sources - mainly 'BigInt.pas' and 'selftest.lpr'. In 'BigInt.pas' I focused on the arithmetic layer, leaving all the algebra,
modular forms etc. off for the moment.

The following is a first feedback on what I see in light of my own experiences. I intend no malice, but I will be straight. As I don't know where you are heading with
your library - focus and intended use case - some of my feedback may not be relevant. In that case just let it pass by.

Let's start with 'BigInt.pas':

* so far I have not seen something obviously bogus in the underlying bigint arithmetic functions
  - there is one quirk in the assembler submul function. In theory this one is incorrect, but in
    practice this will only hit when the limb size of the argument exceeds 2^63. Which is beyond
    memory capacite and therefore can be argued away - a comment re this would be nice though.
   
* personally I would take the assembler stuff out in a separate asm file and link it in if used
  - they tend to clobber up the sources once you start supporting different CPU types/architectures
    and ABI. At the moment it is not so much of a problem, as you only support x86-64 on Win64,
    but you may want to address this sooner than later.
   
* I would also start breaking this up into separate units now! Maintaining this will otherwise
  become a nightmare, whether you do AI assisted programming or not.
  - I personally have units for bit-, limb- and logic-ops, shifts, short arithmetics, arithmetic
    helper functions, long arithmetics, algebra, roots, primes, combinatorics and conversion. But
    even some of these start to become unwieldy again.
   
* Your approach to this unit seems to focus on 'simple'. 'Simple' in the sense of straight and honest algorithm implementation by the book, using system (FPC unleashed) capabilities to provide easy to follow sources. This has some implications
  - you will not win a speed-price (even if you would add e.g. Schönhage-Strassen multiplication on top of Karatsuba and Toom-Cook)
  - you will not win a runtime memory footprint price
If one of the above is a target of yours then you have to do different.
 
Let's look at 'selftest.lpr' now - which is anyway more relevant for you @ the moment I assume.

* relevant limb sizes of arguments under test
  - for basic algorithms (non-recursive, non-thresholded) you somewhere have a loop working over
    the limbs of the argument. Design tests covering sizes up to 4 times the loop-unroll factor -
    which may vary from 1 to 8 usually, depending on pure Pascal or asm implementation
  - for efficient algorithms (recursive with threshold) or algorithms that use efficient functions
    design tests up to 4 times the largest threshold - that guarantees at least 2 recursion levels.
    To keep test time at bay you may want to implement some logarithmic scale on the number of tests
    for a certain size range - such that you have many small, and few large size tests.
   
* you can either verify your library via external oracle or you can bootstrap your own oracle while testing
  - for bigint a suitable external oracle can be GMP, FLINT - they provide sufficient functionality
    and are heavily tested
  - for bigdecimal I know no reliable external oracle - the format sign, integer magnitude + decimal
    exponent is not supported by any library I would trust as external oracle
  - if you test via external oracle you have to make sure that you compare the sign and magnitude,
    do not convert to strings and then compare these
   
* how to bootstrap your own oracle while testing
  - there is an implicit hierarchy for the functions you want to test (see my above comment on
    splitting the library into multiple units to get a picture) - this can be used for bootstrapping
  - for every test of a function you can then use all functions "from below" to build an oracle
    implementing the same functionality in a way that is totally different from the implementation
    used in the function under test <= this is important and sometimes tricky, but always possible
  - on the lowest level you have to trust the compiler to handle its basic types correct or restrict
    tests to cases with known results
  - here are two examples how this works
    - for addition you may want to check correct handling of ripple-carry (this would be the "results
      known in advance" part). The you can test random values adding to itself and compare with left
      shift by one bit. With the equal size stuff covered the non-equal part can be done by extending
      the smaller value with leading 0 limb and then do an equal size addition.
    - for multiplication you start with an oracle function that implements multiplication via bit-
      shift and add (both from lower level and assumed correct) to verify the schoolbook base case.
      Karatsuba and Toom-Cook (equal-size) you can then verify against base case and the general
      (non equal size) mul on large values you can verify by extending the smaller value with leading
      0 limb and do a Toom-Cook (to keep test time at bay).
     
* what to test specifically
  - for addition I already described above - similar for subtraction. The single limb add and sub are
    just variations of these
  - single limb multiplication you can verify with random values plus 0 and 2^k-1 limb multipliers -
    in the case 0 verify that actually an array of 0 limb is generated in the magintude of the results
  - single limb addmul again do random tests but also verify the special cases 0 and 2^k-1 for the
    multipliers
  - single limb submul: similar to single limb addmul
  - long multiplication: random multipliers and multipliers with sequences of 0 or max-value limbs
  - fixed size short division (3-by-2 or 2-by-1 limb): the tricky part in these algorithms is the
    correct detection of the overflow bit (if your algo supports this <= usually this is handled
    by higher layers) and the limb quotient with max-value. Create fitting pairs via multiplication
    and compare with the result from division. To verify the remainder you can modify the product
    by subtracting something <denominator and check if the remainder is <denominator and if
    quot*denom+rmnd = nom. In addition do some tests with random nominator/denominator pairs
    (and 2^k-1 denominators if you are paranoid).
  - division by single limb: similar to fixed size above
  - large division: similar to above but use multipliers with sequences of 0 or max_value limbs and
    random multiplicands. Then divide the product by the multiplicand and do your checks.
   
* if you have implemented all the above and all tests pass, then you can be reasonably sure that your basic bigint arithmetic is ok

* you can then implement a similar approach for bigdecimals using bigint functions assuming they are correct

* always comment your tests with why you think the implemented test cases cover the function under test - it will help in maintenance! Your current test suite is frighteningly low on comments.

Until you have done all of the above I have some time to look closer at the remaining stuff in your library.

Cheers,
MathMan

PS - you can pm me if you have specific questions. This topic may become lengthy and I don't want to divert this thread.

[Fibonacci]

Oh, too bad you had a look right before I pushed a bunch of new changes. I'll go through your post carefully in a moment - but first I wanted to show you the result of the new benchgmp:

Code: Text  [Select][+][-]

1. bigints.pas vs GMP 6.3.0 (64-bit limbs)
2. sanity check ok (1000x900-bit product matches)
3.  
4. (ratio = BigInts / GMP; >1 slower, <1 faster)
5. +---------------------------------+----------------------------------+----------------------------------+----------+------------+
6. | operation                       |                          BigInts |                              GMP |    ratio |   RAM used |
7. +---------------------------------+----------------------------------+----------------------------------+----------+------------+
8. | add (128 digits)                |             0,015 us /   0,000 s |             0,007 us /   0,000 s |     2,3x |       4 KB |
9. | add (1024 digits)               |             0,050 us /   0,000 s |             0,016 us /   0,000 s |     3,1x |       5 KB |
10. | add (16384 digits)              |             0,279 us /   0,000 s |             0,200 us /   0,000 s |     1,4x |      17 KB |
11. | add (262144 digits)             |             4,215 us /   0,000 s |             3,913 us /   0,000 s |     1,1x |     219 KB |
12. | add (1M digits)                 |            15,426 us /   0,000 s |            14,839 us /   0,000 s |     1,0x |     819 KB |
13. | add (10M digits)                |           533,056 us /   0,001 s |           171,426 us /   0,000 s |     3,1x |     8,0 MB |
14. | add (100M digits)               |          9842,063 us /   0,010 s |         10211,813 us /   0,010 s |     1,0x |    79,3 MB |
15. | add (1B digits)                 |         85180,750 us /   0,085 s |         69546,450 us /   0,070 s |     1,2x |   792,1 MB |
16. | addTo (128 digits)              |             0,017 us /   0,000 s |             0,006 us /   0,000 s |     2,7x |       4 KB |
17. | addTo (1024 digits)             |             0,024 us /   0,000 s |             0,017 us /   0,000 s |     1,4x |       5 KB |
18. | addTo (16384 digits)            |             0,215 us /   0,000 s |             0,199 us /   0,000 s |     1,1x |      24 KB |
19. | addTo (262144 digits)           |             3,856 us /   0,000 s |             4,061 us /   0,000 s |     0,9x |     326 KB |
20. | addTo (1M digits)               |            15,467 us /   0,000 s |            15,163 us /   0,000 s |     1,0x |     1,2 MB |
21. | addTo (10M digits)              |           166,164 us /   0,000 s |           164,965 us /   0,000 s |     1,0x |    12,0 MB |
22. | addTo (100M digits)             |          6568,044 us /   0,007 s |          6521,960 us /   0,007 s |     1,0x |   118,9 MB |
23. | addTo (1B digits)               |         67112,800 us /   0,067 s |         66997,700 us /   0,067 s |     1,0x |    1,16 GB |
24. | sub (128 digits)                |             0,016 us /   0,000 s |             0,007 us /   0,000 s |     2,3x |       4 KB |
25. | sub (1024 digits)               |             0,047 us /   0,000 s |             0,018 us /   0,000 s |     2,7x |       5 KB |
26. | sub (16384 digits)              |             0,267 us /   0,000 s |             0,209 us /   0,000 s |     1,3x |      17 KB |
27. | sub (262144 digits)             |             4,141 us /   0,000 s |             4,323 us /   0,000 s |     1,0x |     219 KB |
28. | sub (1M digits)                 |            16,288 us /   0,000 s |            15,810 us /   0,000 s |     1,0x |     819 KB |
29. | sub (10M digits)                |           557,030 us /   0,001 s |           165,526 us /   0,000 s |     3,4x |     8,0 MB |
30. | sub (100M digits)               |          8368,406 us /   0,008 s |          6694,805 us /   0,007 s |     1,2x |    79,3 MB |
31. | sub (1B digits)                 |         98272,200 us /   0,098 s |         68090,700 us /   0,068 s |     1,4x |   792,1 MB |
32. | subTo (128 digits)              |             0,017 us /   0,000 s |             0,007 us /   0,000 s |     2,4x |       4 KB |
33. | subTo (1024 digits)             |             0,024 us /   0,000 s |             0,018 us /   0,000 s |     1,4x |       5 KB |
34. | subTo (16384 digits)            |             0,215 us /   0,000 s |             0,200 us /   0,000 s |     1,1x |      24 KB |
35. | subTo (262144 digits)           |             4,081 us /   0,000 s |             4,024 us /   0,000 s |     1,0x |     326 KB |
36. | subTo (1M digits)               |            15,034 us /   0,000 s |            15,197 us /   0,000 s |     1,0x |     1,2 MB |
37. | subTo (10M digits)              |           165,555 us /   0,000 s |           166,590 us /   0,000 s |     1,0x |    12,0 MB |
38. | subTo (100M digits)             |          6186,084 us /   0,006 s |          6729,475 us /   0,007 s |     0,9x |   118,9 MB |
39. | subTo (1B digits)               |         80674,000 us /   0,081 s |         72769,300 us /   0,073 s |     1,1x |    1,16 GB |
40. | mul (128 digits)                |             0,089 us /   0,000 s |             0,030 us /   0,000 s |     2,9x |       4 KB |
41. | mul (1024 digits)               |             1,263 us /   0,000 s |             1,164 us /   0,000 s |     1,1x |       5 KB |
42. | mul (16384 digits)              |           119,905 us /   0,000 s |            61,170 us /   0,000 s |     2,0x |      17 KB |
43. | mul (262144 digits)             |          7855,817 us /   0,008 s |          2396,390 us /   0,002 s |     3,3x |     219 KB |
44. | mul (1M digits)                 |         41104,567 us /   0,041 s |         11367,609 us /   0,011 s |     3,6x |    13,5 MB |
45. | mul (10M digits)                |        521079,800 us /   0,521 s |        141278,000 us /   0,141 s |     3,7x |   104,8 MB |
46. | mul (100M digits)               |      10515484,500 us /  10,515 s |       1894277,400 us /   1,894 s |     5,6x |    79,3 MB |
47. | mul (100Kx1K digits)            |            93,822 us /   0,000 s |           105,157 us /   0,000 s |     0,9x |      46 KB |
48. | div (128 / 64 digits)           |             0,068 us /   0,000 s |             0,265 us /   0,000 s |     0,3x |       4 KB |
49. | div (1024 / 512 digits)         |             0,711 us /   0,000 s |             0,471 us /   0,000 s |     1,5x |       4 KB |
50. | div (16384 / 8192 digits)       |            75,629 us /   0,000 s |            44,093 us /   0,000 s |     1,7x |      14 KB |
51. | div (262144 / 131072 digits)    |          6855,850 us /   0,007 s |          2203,369 us /   0,002 s |     3,1x |     165 KB |
52. | div (1M / 500K digits)          |         51192,933 us /   0,051 s |         11145,542 us /   0,011 s |     4,6x |     615 KB |
53. | div (10M / 5M digits)           |       1125735,000 us /   1,126 s |        158257,000 us /   0,158 s |     7,1x |    30,8 MB |
54. | div (100M / 50M digits)         |      25086734,700 us /  25,087 s |       2037606,300 us /   2,038 s |    12,3x |    59,4 MB |
55. | sqr (128 digits)                |             0,082 us /   0,000 s |             0,022 us /   0,000 s |     3,7x |       4 KB |
56. | sqr (1024 digits)               |             1,172 us /   0,000 s |             0,655 us /   0,000 s |     1,8x |       4 KB |
57. | sqr (16384 digits)              |           104,774 us /   0,000 s |            44,058 us /   0,000 s |     2,4x |      10 KB |
58. | sqr (262144 digits)             |          6825,437 us /   0,007 s |          1291,531 us /   0,001 s |     5,3x |     111 KB |
59. | sqr (1M digits)                 |         28274,360 us /   0,028 s |          6312,857 us /   0,006 s |     4,5x |    13,2 MB |
60. | sqr (10M digits)                |        388331,100 us /   0,388 s |         95354,100 us /   0,095 s |     4,1x |   100,8 MB |
61. | divmod (128 / 64 digits)        |             0,167 us /   0,000 s |             0,265 us /   0,000 s |     0,6x |    96,8 MB |
62. | divmod (1024 / 512 digits)      |             0,844 us /   0,000 s |             0,710 us /   0,000 s |     1,2x |    96,8 MB |
63. | divmod (16384 / 8192 digits)    |            77,129 us /   0,000 s |            55,883 us /   0,000 s |     1,4x |    96,8 MB |
64. | divmod (262144 / 131072 digits) |          6562,040 us /   0,007 s |          2476,149 us /   0,002 s |     2,7x |    96,9 MB |
65. | divmod (1M / 500K digits)       |         49122,433 us /   0,049 s |         12676,745 us /   0,013 s |     3,9x |    97,4 MB |
66. | divmod (10M / 5M digits)        |       1057814,500 us /   1,058 s |        192352,400 us /   0,192 s |     5,5x |   102,8 MB |
67. | divmod (100M / 50M digits)      |      25286824,700 us /  25,287 s |       2473781,800 us /   2,474 s |    10,2x |    59,4 MB |
68. | toString (128 digits)           |             0,706 us /   0,000 s |             0,246 us /   0,000 s |     2,9x |       4 KB |
69. | toString (1024 digits)          |             6,937 us /   0,000 s |             3,248 us /   0,000 s |     2,1x |       7 KB |
70. | toString (16384 digits)         |           297,653 us /   0,000 s |           169,630 us /   0,000 s |     1,8x |      43 KB |
71. | toString (262144 digits)        |         19571,814 us /   0,020 s |          9570,486 us /   0,010 s |     2,0x |     632 KB |
72. | parse (128 digits)              |             0,670 us /   0,000 s |             0,310 us /   0,000 s |     2,2x |     261 KB |
73. | parse (1024 digits)             |             4,845 us /   0,000 s |             2,926 us /   0,000 s |     1,7x |     262 KB |
74. | parse (16384 digits)            |           168,440 us /   0,000 s |           100,402 us /   0,000 s |     1,7x |     284 KB |
75. | parse (262144 digits)           |          9829,407 us /   0,010 s |          4686,627 us /   0,005 s |     2,1x |     632 KB |
76. | modPow (128 digits)             |            50,627 us /   0,000 s |            25,861 us /   0,000 s |     2,0x |     261 KB |
77. | modPow (1024 digits)            |         10192,415 us /   0,010 s |          8817,519 us /   0,009 s |     1,2x |     262 KB |
78. | modPow (16384 digits, 4k-bit e) |       1675009,600 us /   1,675 s |        700189,900 us /   0,700 s |     2,4x |     275 KB |
79. | gcd (128 digits)                |             3,083 us /   0,000 s |             1,006 us /   0,000 s |     3,1x |     261 KB |
80. | gcd (1024 digits)               |            29,143 us /   0,000 s |            10,666 us /   0,000 s |     2,7x |     262 KB |
81. | gcd (16384 digits)              |          1860,269 us /   0,002 s |           953,516 us /   0,001 s |     2,0x |     275 KB |
82. | gcd (262144 digits)             |        183223,100 us /   0,183 s |         50438,567 us /   0,050 s |     3,6x |     476 KB |
83. | gcd (1M digits)                 |       1364238,700 us /   1,364 s |        298954,300 us /   0,299 s |     4,6x |     1,1 MB |
84. +---------------------------------+----------------------------------+----------------------------------+----------+------------+
85.  
86. (sink = 787874835)

[Fibonacci]

Ok, so first - thank you. Genuinely. You said you'd be straight and that's exactly what I wanted; a fresh library needs someone poking at the arithmetic with an adversarial eye, not polite noises. And "nothing obviously bogus in the underlying arithmetic" is about the best sentence I could have hoped to read at this stage, so thanks for cutting straight to it.

Going through your points:

The submul quirk. Good catch, and you're right - it only bites when the limb count passes 2^63, which means an array larger than addressable memory, so it can never fire in practice. But "can't happen" is not the same as "documented", so I'll add a comment on the n < 2^63 assumption right at the kernel. Cheap and honest.

"Focus on simple / schoolbook / won't win a speed price" - and your earlier point that schoolbook loses badly once you hit million/billion-digit numbers. Both completely fair for the snapshot you read. You looked at the tree around the Toom-4 commit, where the multiply ladder topped out at Karatsuba -> Toom-3 -> Toom-4 and there was no FFT-class path at all. That has since changed quite a bit. Landed after that point:

• single-prime, then a 3-prime NTT (64-bit-limb coefficients, Garner CRT) - the FFT-class multiply for very large operands
• Burnikel-Ziegler recursive division on top of the fast multiply
• a subquadratic half-gcd
• 4x-unrolled x86-64 limb kernels, and modPow routing its Montgomery products through the fast multiply

So it is no longer schoolbook-that-explodes at the top end - the large-size range you flagged is precisely what those target, and the refreshed GMP benchmark in the README now runs out to a billion digits so that behaviour is actually visible.

But I want to be clear that I'm not chasing a "win" here, because in the sense that matters to me I've already got what I wanted. This is Pascal - I'm never going to beat well-tuned C, let alone something that's asm all the way down, and that was never the goal. The speed is more than satisfying for me, and everything I actually wanted from a bignum, BigInts delivers. The part I care about is that it behaves like a normal type: real operators, all of them, so a BigInt drops in wherever an Integer or Int64 would go and does the obvious thing. Anything you can do with a built-in integer, you can do with a BigInt - no ceremony, no mental model to learn. There's no real documentation and there doesn't need to be; a README and a handful of examples, and you're productive. That simplicity of use is the actual headline feature, and the fast layer is just there so "simple to use" doesn't turn into "falls over at scale".

Constant time. You pinned this earlier and you were right that modPowSec on its own is not enough. Since then the genuinely constant-time path landed as a separate type, TModRingSec: fixed-width limbs, branchless conditional subtract, no normalization, no early exits, scratch wiped on release. It sits in the modular layer you explicitly skipped, so you wouldn't have seen it - modPowSec now rides on that rather than on the variable-time schoolbook path. Remaining boundary caveats (the entry reduce of an unreduced base, and value magnitude leaking through limb count at the boundary) are documented in the type header rather than swept under "side-channel resistant".

Splitting the asm out / breaking into separate units. Here I'll respectfully push back, because the single unit is not something I haven't gotten around to - it's the point. Simplicity is what I'm optimizing for, and "one unit" is part of that simplicity: one file, one uses, drop it in, done. To me the code also reads well and stays maintainable as it is, so a split would trade the thing I value for a structure I don't need.

On the asm specifically: the only assembler is what's already there, x86-64 and a bit of i386, and nothing more is coming - most likely ever. Everything else runs the pure-Pascal fallback, which is complete and self-contained, so the "asm clobbers the sources across many CPUs/ABIs" problem is one I've sidestepped by simply not chasing many targets. The one exception I'd leave open: aarch64 is a genuinely different instruction set, so if I ever end up with hardware for it, a dedicated aarch64 path might appear. Short of that, the asm surface stays exactly as it is.

The tests. Fair hit - selftest is thin and under-commented, and honestly a good chunk of your methodology writeup is deeper in the weeds than where I am right now, so I won't pretend I've internalized all of it yet. But the direction is clearly right and I'll take it on board: more coverage tuned to the actual thresholds and to the ugly limb patterns, comparing sign and magnitude rather than strings, and a comment on each case saying why it covers the function.

One aside on your "at the lowest level you have to trust the compiler, or restrict to known results" point. That trust turned out to be the interesting part: writing BigInts surfaced a whole series of real compiler bugs. They're fixed in Unleashed now, and I filed issues on GitLab against stock FPC for them. So "trust the compiler with its basic types" was not a freebie here - the library was itself a fairly effective codegen fuzzer. One of those issues I even boiled down to a side-by-side Delphi vs FPC comparison: Delphi generated correct code, FPC miscompiled it - and had done so for decades. How does a bug like that survive that long? Presumably nobody had hit that exact use case before, or assumed "that's how it's supposed to work", or just couldn't be bothered to file it. FPC is full of bugs, unfortunately.

On the oracle: GMP is exactly what I'm already cross-checking against, comparing magnitude not strings. I hadn't heard of FLINT until you mentioned it - I'll take a look, could be a stronger reference at the top end. For BigDecimal I'll have to take your word that there's no external oracle worth trusting in that sign/mantissa/exponent format - I haven't gone looking myself - so if nothing suitable turns up, that layer just gets bootstrapped from the verified BigInt core.

Realistically I'm not in a hurry on any of this. At this stage I consider the unit essentially finished - maybe minor fixes here and there, and at some point I'll likely come back to fill in the missing tests properly, against GMP/FLINT and whatever I can find for decimals. But the honest trigger for that will probably be the first actual bug. As long as it works, I don't see problems, and - as you found - you don't see anything obviously wrong either, I'm comfortable calling it good for now.

Thanks again for spending the time on a library this size. Genuinely useful, and I'll take you up on the PM offer once I hit something specific.

[creaothceann]

New intrinsic: SwapValues

On by default in {$mode unleashed}.

A compiler intrinsic that swaps the values of two variables.

Would it be easy to add a second mode for SwapValues that isn't a bitwise swap, but just syntactic sugar for a swap with a variable created behind the scenes? That would allow it to be used with properties (just like Inc/Dec).

Also, it seems that indexed labels are not highlighted like regular labels?

[Fibonacci]

Would it be easy to add a second mode for SwapValues that isn't a bitwise swap, but just syntactic sugar for a swap with a variable created behind the scenes? That would allow it to be used with properties (just like Inc/Dec).

Also, it seems that indexed labels are not highlighted like regular labels?

Indexed labels: fixed. Also improved a related error message while I was at it - if you declare label mylabel[3] (or mylabel[0..2]) and then write mylabel: without an index, instead of:

Code: Text  [Select][+][-]

1. project1.lpr(19,10) Error: Parser - Syntax Error
2. project1.lpr(19,10) Error: Syntax error, ";" expected but ":" found

you now get:

Code: Text  [Select][+][-]

1. project1.lpr(19,10) Error: Label "mylabel" is an indexed label, an index is required: "mylabel[...]"

Clearer, and it points at the actual problem.


SwapValues() for non-addressable values: doable - addressable operands would keep the in-place swap, non-addressable ones would go through a hidden temp + getter/setter, same way Inc/Dec already work on properties. Caveats:

- 2 getter + 2 setter calls instead of zero - if the accessors do real work (notify, invalidate, logging), you pay for it on every swap
- it's not atomic in any sense - a setter runs arbitrary code and can observe the half-swapped state
- requires both read and write - read-only properties stay an error
- same syntax, two different behaviors depending on the operand - the cost is visible only if you know what the property does

Acceptable list for you? If so, implementation shouldn't be a problem.

I'd also add a hint whenever the temporary path kicks in, so the accessor calls aren't completely invisible: Hint: SwapValues on "obj.A" is not an in-place swap: it uses a temporary and calls the getter and setter of each property operand. Not a warning - Inc/Dec don't warn either, and this would fire on perfectly intentional code.