Big Integers in Turbo Pascal 3.01A (6)
22nd November 2023: This post has been sat in my drafts folder since the start of August … I really must learn to finish what I start!
While much of Europe has been baking in a man-made climate change hell this summer, the UK has been remarkably cool and wet since the start of July. There’s no real end to this weather in sight, but I have my fingers crossed for September as I have plans.
With gnuing therefore curtailed, I’ve been playing with my Big Integer library. I have made some progress. The current version manages these prime number generation times on an original Raspberry Pi B compared with the code as I left it at the start of June.
| All primes < n | Version 1 BigInt type | Version 2 BigInt type | Performance improvement |
|---|---|---|---|
| 100 | 0.07s | 0.02s | 71% |
| 1,000 | 0.97s | 0.11s | 89% |
| 10,000 | 16.5s | 1.4s | 92% |
| 32,000 (*) | 71.0s | 3.6s | 95% |
| 100,000 | 302s | 120s | 60% |
| 250,000 | – | 635s | – |
| 1,000,000 | 5,993s | 6,206s | -3.6% |
The table should give an immediate clue to one of the improvements I’ve made. By checking if the outcome of an operation is likely to fall within the normal integer range (as defined by the Z80 implementation of Turbo Pascal), the library converts BigInts to integers and back again, so that the standard maths operators can be used.
I made a change to the integer square root algorithm to start off with a better guess for the root (rather than simply dividing the operand by 2), based on the number of digits in the operand. This has the impact of reducing the number of iterations required for the root to be found.
The third big change was to implement the Karatsuba multiplication algorithm. This has complexity O(n1.58) rather than O(n2), where n = number of digits. This should make significant savings on truly large integers.
I was able to simplify the comparison operators by taking advantage of the way Turbo Pascal handles and compares strings. I also decided to inline the zapzeros and nines complement functions – which also helped improve execution time.
The cumulative impact of these chnages brought the initial runtime for primes up to 100,000 down from 250s to the 120s noted in the table above. I’m somewhat confused by the 1,000,000 benchmark, however, as it’s slower than my original implementation, My best guess is that I converted the time taken into seconds wrongly on the original benchmark, rather than it being a genuine result. I guess I ought to go back and check …
Transferring the code back to the RC2014 gave these results:
| All primes < n | Version 1 BigInt type | Version 2 BigInt type | Performance improvement |
|---|---|---|---|
| 100 | 73s | 6s | 82% |
| 500 | 912s | – | – |
| 1,000 | – | 148s | – |
| 10,000 | – | 2,767s | – |
| 32,000 (*) | – | 7,560s | – |
Much better, but still not very practical!
The library, test programs and documentation can be found here – https://github.com/psychotimmy/PascalBigIntegers
Where next? I’m convinced that the subtraction and addition functions can be improved – probably not to the same degree that the multiplication code has been, but nonetheless useful. Hopefully I won’t have time to do that before winter sets in …