Repository navigation
Expand file tree
/
Copy pathbigints.pas
More file actions
13910 lines (12827 loc) · 427 KB
/
Copy pathbigints.pas
File metadata and controls
13910 lines (12827 loc) · 427 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
{ BigInts - arbitrary precision integers for Unleashed Pascal
Four value types with full operator coverage and no size limit:
UBigInt - unsigned big integer (raises ERangeError on negative results)
BigInt - signed big integer, two's complement semantics for bitwise ops
BigDecimal - decimal float over the same core: BigInt mantissa * 10^exp
BigRational - exact fraction: normalized BigInt num/den pair
Two Montgomery contexts over a fixed odd modulus, for many products against one modulus:
TModRing - fast modular arithmetic (RSA/ECC-style workloads)
TModRingSec - constant-time hardened counterpart for secret-dependent work
Free helpers:
addTo / subTo - in-place dst := a +/- b, reusing dst's buffer
BigIntRandomSeed / BigIntRandomize - seed the generators deterministically / from OS entropy }
{ Copyright (c) 2026 @fibodevy / https://github.com/fibodevy
This Source Code Form is subject to the terms of the Mozilla Public
License, v. 2.0. If a copy of the MPL was not distributed with this
file, You can obtain one at https://mozilla.org/MPL/2.0/ }
unit BigInts;
{$mode unleashed}
// asm inner loops on x86_64; comment out to build the fully portable pure
// Pascal core (64-bit limbs when the compiler provides a native UInt128 on a
// 64-bit CPU, 32-bit limbs otherwise)
{$define USEASM}
{$if defined(CPUX86_64) and defined(USEASM)}{$define BIGINT_ASM}{$endif}
{$if defined(CPU386) and defined(USEASM)}{$define BIGINT_ASM32}{$endif}
// the x86_64 kernels are written against the Microsoft x64 argument registers;
// on every other x86_64 target the SysV ABI applies and a prologue shuffles the
// four integer arguments into that layout
{$if defined(BIGINT_ASM) and not defined(WINDOWS)}{$define BIGINT_ABI_SYSV}{$endif}
// limb arithmetic relies on modular 32-bit/64-bit wraparound
{$q-}{$r-}
// dynamic array locals are nil-initialized by the compiler and tuple
// destructuring discards are intentional; these flow hints are noise here
{$warn 5089 off}{$warn 5091 off}{$warn 5092 off}{$warn 5093 off}{$warn 5094 off}{$warn 5027 off}
interface
// native UInt128 (compilers that provide it): double-limb products and
// the PCG64 state advance become single inline multiplies instead of calls
// (declared() only resolves system types from the interface part on)
// BIGINT_HAS_INT128 gates the public Int128/UInt128 conversions (they need
// only the type); BIGINT_INT128 additionally requires a 64-bit CPU and drives
// the inline double-limb product and PCG64 advance; BIGINT_PP128 marks the
// pure Pascal build that still gets 64-bit limbs, with UInt128 double-limb
// temps in the portable kernels
{$if declared(UInt128)}{$define BIGINT_HAS_INT128}{$if defined(CPU64)}{$define BIGINT_INT128}{$endif}{$endif}
{$if defined(BIGINT_INT128) and not defined(BIGINT_ASM)}{$define BIGINT_PP128}{$endif}
{$if defined(BIGINT_ASM) or defined(BIGINT_PP128)}{$define BIGINT_LIMB64}{$endif}
uses SysUtils;
type
// raised for domain errors: negative exponent, no modular inverse, ...
// (div by zero raises EDivByZero, overflows in conversions raise ERangeError,
// parse errors raise EConvertError - same classes plain integers use)
EBigIntError = class(Exception);
// generator behind random/randomBelow/randomRange/randomPrime; rngSystem is
// the RandSeed-driven System.Random stream, rngOS reads OS entropy per call
TBigIntRngAlgo = (rngXoshiro256ss, rngPcg64, rngSplitMix64, rngSystem, rngOS);
// internal storage: little-endian array of limbs (64-bit on 64-bit CPUs,
// 32-bit elsewhere), highest limb nonzero, nil = 0
{$ifdef BIGINT_LIMB64}
TBigIntLimb = QWord;
{$else}
TBigIntLimb = DWord;
{$endif}
TBigIntLimbs = array of TBigIntLimb;
PBigIntLimb = ^TBigIntLimb;
const
// values up to this many limbs (512 bits) live inline in the record with no
// heap allocation; larger ones spill into a refcounted block. tunable
{$ifdef BIGINT_LIMB64}
BIGINT_INLINE_LIMBS = 8;
{$else}
BIGINT_INLINE_LIMBS = 16;
{$endif}
type
{ UBigInt - unsigned arbitrary precision integer }
UBigInt = record
private
// small-value optimization: up to BIGINT_INLINE_LIMBS limbs sit inline
// with no allocation, larger values spill into the fArr limb array (nil =
// value lives inline); fLen is the significant limb count (0 = zero,
// highest limb nonzero). fLimbs is a property view over either storage:
// for spilled values it shares fArr with no copy, so large-value paths
// cost the same as a plain limb-array field, while small values never
// touch the heap. fArr is compiler-managed (refcounted dynarray)
fInline: array[0..BIGINT_INLINE_LIMBS - 1] of TBigIntLimb;
fArr: TBigIntLimbs;
fLen: SizeInt;
function dataPtr: PBigIntLimb; inline;
function getLimbs: TBigIntLimbs;
procedure setLimbs(const v: TBigIntLimbs);
function getBitProp(i: LongWord): boolean; inline;
procedure putBitProp(i: LongWord; v: boolean); inline;
procedure fillBytesLE(dst: PByte; n: SizeInt);
procedure fillBytesBE(dst: PByte; n: SizeInt);
property fLimbs: TBigIntLimbs read getLimbs write setLimbs;
public
// fArr is a managed field, so copy/addref/finalize are compiler-default;
// Initialize only zeroes the plain fields the compiler would leave alone
class operator Initialize(var x: UBigInt);
// conversions in (negative values raise ERangeError)
class operator :=(x: Int64): UBigInt;
class operator :=(x: QWord): UBigInt;
class operator :=(const s: string): UBigInt;
class operator explicit(d: Double): UBigInt;
// exact integer paths for typecasts, so UBigInt(q) never rounds via Double
class operator explicit(x: Int64): UBigInt;
class operator explicit(x: QWord): UBigInt;
// conversions out (values that do not fit raise ERangeError)
class operator explicit(const a: UBigInt): Int64;
class operator explicit(const a: UBigInt): QWord;
class operator explicit(const a: UBigInt): LongInt;
class operator explicit(const a: UBigInt): LongWord;
class operator explicit(const a: UBigInt): Double;
class operator explicit(const a: UBigInt): string;
// arithmetic
class operator +(const a, b: UBigInt): UBigInt;
class operator +(const a: UBigInt; b: Int64): UBigInt;
class operator +(a: Int64; const b: UBigInt): UBigInt;
class operator -(const a, b: UBigInt): UBigInt;
class operator -(const a: UBigInt; b: Int64): UBigInt;
class operator -(a: Int64; const b: UBigInt): UBigInt;
class operator *(const a, b: UBigInt): UBigInt;
class operator *(const a: UBigInt; b: Int64): UBigInt;
class operator *(a: Int64; const b: UBigInt): UBigInt;
class operator div(const a, b: UBigInt): UBigInt;
class operator div(const a: UBigInt; b: Int64): UBigInt;
class operator mod(const a, b: UBigInt): UBigInt;
class operator mod(const a: UBigInt; b: Int64): UBigInt;
// "/" is integer division here, same thing as div (C-family convention)
class operator /(const a, b: UBigInt): UBigInt;
class operator **(const a, b: UBigInt): UBigInt;
class operator **(const a: UBigInt; e: Int64): UBigInt;
class operator inc(const a: UBigInt): UBigInt;
class operator dec(const a: UBigInt): UBigInt;
// shifts (negative count raises ERangeError)
class operator shl(const a: UBigInt; n: Int64): UBigInt;
class operator shr(const a: UBigInt; n: Int64): UBigInt;
// bitwise ("not" is intentionally absent: the infinite-width complement of an
// unsigned value is not representable - use BigInt or complement(width))
class operator and(const a, b: UBigInt): UBigInt;
class operator or(const a, b: UBigInt): UBigInt;
class operator xor(const a, b: UBigInt): UBigInt;
// comparisons
class operator =(const a, b: UBigInt): boolean;
class operator =(const a: UBigInt; b: Int64): boolean;
class operator =(a: Int64; const b: UBigInt): boolean;
class operator <>(const a, b: UBigInt): boolean;
class operator <>(const a: UBigInt; b: Int64): boolean;
class operator <>(a: Int64; const b: UBigInt): boolean;
class operator <(const a, b: UBigInt): boolean;
class operator <(const a: UBigInt; b: Int64): boolean;
class operator <(a: Int64; const b: UBigInt): boolean;
class operator <=(const a, b: UBigInt): boolean;
class operator <=(const a: UBigInt; b: Int64): boolean;
class operator <=(a: Int64; const b: UBigInt): boolean;
class operator >(const a, b: UBigInt): boolean;
class operator >(const a: UBigInt; b: Int64): boolean;
class operator >(a: Int64; const b: UBigInt): boolean;
class operator >=(const a, b: UBigInt): boolean;
class operator >=(const a: UBigInt; b: Int64): boolean;
class operator >=(a: Int64; const b: UBigInt): boolean;
// formatting
function toString: string;
function toString(base: integer): string;
function toHex: string;
function toBin: string;
function toOct: string;
// numeric conversions (raise ERangeError when the value does not fit)
function toInt8: Int8;
function toUInt8: UInt8;
function toInt16: Int16;
function toUInt16: UInt16;
function toInt32: Int32;
function toUInt32: UInt32;
function toInt64: Int64;
function toUInt64: UInt64;
{$ifdef BIGINT_HAS_INT128}
function toInt128: Int128;
function toUInt128: UInt128;
{$endif}
function toDouble: Double;
// does the value fit in each native integer width
function fitsInInt8: boolean;
function fitsInUInt8: boolean;
function fitsInInt16: boolean;
function fitsInUInt16: boolean;
function fitsInInt32: boolean;
function fitsInUInt32: boolean;
function fitsInInt64: boolean;
function fitsInUInt64: boolean;
{$ifdef BIGINT_HAS_INT128}
function fitsInInt128: boolean;
function fitsInUInt128: boolean;
{$endif}
// predicates
function isZero: boolean;
function isOne: boolean;
function isEven: boolean;
function isOdd: boolean;
function isPowerOfTwo: boolean;
function sign: integer;
// bit access
function bitLength: LongWord;
function popCount: LongWord;
function lowestSetBit: Int64;
function testBit(i: LongWord): boolean;
procedure setBit(i: LongWord);
procedure clearBit(i: LongWord);
procedure flipBit(i: LongWord);
// complement of the low "width" bits (finite-width bitwise not)
function complement(width: LongWord): UBigInt;
property bits[i: LongWord]: boolean read getBitProp write putBitProp;
// comparison helpers
function compare(const other: UBigInt): integer;
function equals(const other: UBigInt): boolean;
// constant-time variants: no data-dependent branches or early exits, the
// running time depends only on the limb counts (for secret comparisons)
function equalsCT(const other: UBigInt): boolean;
function compareCT(const other: UBigInt): integer;
// zero the limb storage before releasing it (skips buffers shared with
// other values), then set the value to 0
procedure secureClear;
function min(const other: UBigInt): UBigInt;
function max(const other: UBigInt): UBigInt;
// division helpers
function divMod(const d: UBigInt): (q, r: UBigInt);
function ceilDiv(const d: UBigInt): UBigInt;
// misc
procedure swap(var other: UBigInt);
// parsing (auto-detects prefixes: $ 0x hex, % 0b binary, & 0o octal; "_" separators allowed)
class function parse(const s: string): UBigInt; static;
class function parse(const s: string; base: integer): UBigInt; static;
class function tryParse(const s: string; out v: UBigInt): boolean; static;
class function tryParse(const s: string; base: integer; out v: UBigInt): boolean; static;
// math
function sqr: UBigInt;
function sqrt: UBigInt;
function nthRoot(n: LongWord): UBigInt;
function nthRootRem(n: LongWord): (root, rem: UBigInt);
function isKthPower(k: LongWord): boolean;
function pow(e: LongWord): UBigInt;
function modPow(const e, m: UBigInt): UBigInt;
function modInverse(const m: UBigInt): UBigInt;
function gcd(const other: UBigInt): UBigInt;
function lcm(const other: UBigInt): UBigInt;
// extras: number theory
function jacobi(const n: UBigInt): integer;
function kronecker(const n: UBigInt): integer;
function modSqrt(const p: UBigInt): UBigInt;
// one k-th root modulo an odd prime (Adleman-Manders-Miller); raises when
// none exists
function nthRootMod(k: LongWord; const p: UBigInt): UBigInt;
// square roots modulo a composite: every solution, via factor+lift+CRT
function sqrtModN(const n: UBigInt): array of UBigInt;
// baby-step giant-step discrete log: least x with self^x = target (mod m),
// or -1 when none exists below the modulus order
function discreteLog(const target, m: UBigInt): Int64;
// least k > 0 with self^k = 1 (mod m); self must be coprime to m
function multiplicativeOrder(const m: UBigInt): UBigInt;
function isPrimitiveRoot(const m: UBigInt): boolean;
// smallest primitive root modulo self (exists for 1, 2, 4, p^k, 2*p^k)
function primitiveRoot: UBigInt;
function isPerfectSquare: boolean;
function sqrtRem: (root, rem: UBigInt);
function factorize: array of (p: UBigInt; e: LongWord);
// multiplicative functions, all read off the factorization
function eulerPhi: UBigInt;
function carmichaelLambda: UBigInt;
function moebius: integer;
function sigma(k: LongWord = 1): UBigInt;
function tau: UBigInt;
function radical: UBigInt;
function divisors: array of UBigInt;
function isSquarefree: boolean;
function isPerfect: boolean;
function isCarmichael: boolean;
// primes: isProbablePrime is Miller-Rabin (deterministic below 3.3e24, then
// random rounds); isPrime is Baillie-PSW (no known counterexample)
function isProbablePrime(rounds: integer = 24): boolean;
function isPrime: boolean;
function nextPrime: UBigInt;
function prevPrime: UBigInt;
// bytes, little/big endian magnitude; zero gives an empty array
function toBytesLE: TBytes;
function toBytesBE: TBytes;
// fixed width: zero-padded to len bytes (ERangeError when the value does
// not fit), for protocols with fixed-size fields
function toBytesLE(len: SizeInt): TBytes;
function toBytesBE(len: SizeInt): TBytes;
class function fromBytesLE(const bytes: TBytes): UBigInt; static;
class function fromBytesBE(const bytes: TBytes): UBigInt; static;
class function fromBytesLE(src: Pointer; len: SizeInt): UBigInt; static;
class function fromBytesBE(src: Pointer; len: SizeInt): UBigInt; static;
// magnitude bytes packed in a string container (raw bytes, not digit text)
function toByteStringLE: string;
function toByteStringBE: string;
class function fromByteStringLE(const s: string): UBigInt; static;
class function fromByteStringBE(const s: string): UBigInt; static;
// allocates dst with GetMem and fills it with the magnitude bytes; the
// caller must release it with FreeMem. returns the byte count
function toBytesLE(out dst: Pointer): SizeInt;
function toBytesBE(out dst: Pointer): SizeInt;
// misc
function digitCount: LongWord;
function toStringGrouped(sep: char = '_'; groupSize: integer = 3): string;
function hashCode: DWord;
// constants and generators
class function zero: UBigInt; static;
class function one: UBigInt; static;
class function two: UBigInt; static;
class function ten: UBigInt; static;
class function pow2(n: LongWord): UBigInt; static;
class function random(bits: LongWord): UBigInt; static;
class function randomBelow(const bound: UBigInt): UBigInt; static;
class function randomRange(const lo, hi: UBigInt): UBigInt; static;
class function randomPrime(bits: LongWord; rounds: integer = 24): UBigInt; static;
// CSPRNG variants: bytes come straight from the OS entropy source with no
// seedable generator in between (key material); raise EBigIntError when
// the OS source is unavailable
class function randomSecure(bits: LongWord): UBigInt; static;
class function randomSecureBelow(const bound: UBigInt): UBigInt; static;
class function randomSecureRange(const lo, hi: UBigInt): UBigInt; static;
class function randomSecurePrime(bits: LongWord; rounds: integer = 24): UBigInt; static;
// safe prime: p and (p-1)/2 both prime; strong prime: p-1 and p+1 each have
// a large prime factor (RSA/DH key generation)
class function randomSafePrime(bits: LongWord): UBigInt; static;
class function randomStrongPrime(bits: LongWord): UBigInt; static;
// exact prime counting by a segmented sieve (practical to ~1e10)
class function primePi(n: QWord): QWord; static;
class function primeCount(lo, hi: QWord): QWord; static;
class function factorial(n: LongWord): UBigInt; static;
class function fibonacci(n: LongWord): UBigInt; static;
class function lucas(n: LongWord): UBigInt; static;
class function binomial(n, k: LongWord): UBigInt; static;
// C(n, k) mod prime p for arbitrarily large n, k via the Lucas theorem;
// cost grows with min(k, n-k) taken per base-p digit
class function binomialMod(const n, k, p: UBigInt): UBigInt; static;
class function multinomial(const ks: array of LongWord): UBigInt; static;
class function risingFactorial(const x: UBigInt; n: LongWord): UBigInt; static;
class function fallingFactorial(const x: UBigInt; n: LongWord): UBigInt; static;
class function catalan(n: LongWord): UBigInt; static;
class function primorial(n: LongWord): UBigInt; static;
class function subfactorial(n: LongWord): UBigInt; static;
class function bell(n: LongWord): UBigInt; static;
class function stirling2(n, k: LongWord): UBigInt; static;
class function partitions(n: LongWord): UBigInt; static;
end;
{ BigInt - signed arbitrary precision integer, sign-magnitude storage;
bitwise operators and bit access use two's complement semantics with
infinite sign extension (like Python ints), div/mod truncate like Pascal }
BigInt = record
private
// same inline storage as UBigInt (see there), plus a sign flag
fInline: array[0..BIGINT_INLINE_LIMBS - 1] of TBigIntLimb;
fArr: TBigIntLimbs;
fLen: SizeInt;
fNeg: boolean;
function dataPtr: PBigIntLimb; inline;
function getLimbs: TBigIntLimbs;
procedure setLimbs(const v: TBigIntLimbs);
function getBitProp(i: LongWord): boolean; inline;
procedure putBitProp(i: LongWord; v: boolean); inline;
procedure fillBytesLE(dst: PByte; n: SizeInt);
property fLimbs: TBigIntLimbs read getLimbs write setLimbs;
public
class operator Initialize(var x: BigInt);
// conversions in
class operator :=(x: Int64): BigInt;
class operator :=(x: QWord): BigInt;
class operator :=(const s: string): BigInt;
class operator :=(const u: UBigInt): BigInt;
class operator explicit(d: Double): BigInt;
// exact integer paths for typecasts, so BigInt(q) never rounds via Double
class operator explicit(x: Int64): BigInt;
class operator explicit(x: QWord): BigInt;
// conversions out (values that do not fit raise ERangeError)
class operator explicit(const a: BigInt): Int64;
class operator explicit(const a: BigInt): QWord;
class operator explicit(const a: BigInt): LongInt;
class operator explicit(const a: BigInt): LongWord;
class operator explicit(const a: BigInt): Double;
class operator explicit(const a: BigInt): string;
class operator explicit(const a: BigInt): UBigInt;
// arithmetic
class operator +(const a, b: BigInt): BigInt;
class operator +(const a: BigInt; b: Int64): BigInt;
class operator +(a: Int64; const b: BigInt): BigInt;
class operator -(const a, b: BigInt): BigInt;
class operator -(const a: BigInt; b: Int64): BigInt;
class operator -(a: Int64; const b: BigInt): BigInt;
class operator *(const a, b: BigInt): BigInt;
class operator *(const a: BigInt; b: Int64): BigInt;
class operator *(a: Int64; const b: BigInt): BigInt;
class operator div(const a, b: BigInt): BigInt;
class operator div(const a: BigInt; b: Int64): BigInt;
class operator mod(const a, b: BigInt): BigInt;
class operator mod(const a: BigInt; b: Int64): BigInt;
// "/" is integer division here, same thing as div (C-family convention)
class operator /(const a, b: BigInt): BigInt;
class operator **(const a, b: BigInt): BigInt;
class operator **(const a: BigInt; e: Int64): BigInt;
class operator inc(const a: BigInt): BigInt;
class operator dec(const a: BigInt): BigInt;
// unary
class operator -(const a: BigInt): BigInt;
class operator +(const a: BigInt): BigInt;
// shifts: shl keeps the sign, shr is arithmetic (rounds toward -infinity)
class operator shl(const a: BigInt; n: Int64): BigInt;
class operator shr(const a: BigInt; n: Int64): BigInt;
// bitwise, two's complement with infinite sign extension; not x = -x-1
class operator and(const a, b: BigInt): BigInt;
class operator or(const a, b: BigInt): BigInt;
class operator xor(const a, b: BigInt): BigInt;
class operator not(const a: BigInt): BigInt;
// comparisons
class operator =(const a, b: BigInt): boolean;
class operator =(const a: BigInt; b: Int64): boolean;
class operator =(a: Int64; const b: BigInt): boolean;
class operator <>(const a, b: BigInt): boolean;
class operator <>(const a: BigInt; b: Int64): boolean;
class operator <>(a: Int64; const b: BigInt): boolean;
class operator <(const a, b: BigInt): boolean;
class operator <(const a: BigInt; b: Int64): boolean;
class operator <(a: Int64; const b: BigInt): boolean;
class operator <=(const a, b: BigInt): boolean;
class operator <=(const a: BigInt; b: Int64): boolean;
class operator <=(a: Int64; const b: BigInt): boolean;
class operator >(const a, b: BigInt): boolean;
class operator >(const a: BigInt; b: Int64): boolean;
class operator >(a: Int64; const b: BigInt): boolean;
class operator >=(const a, b: BigInt): boolean;
class operator >=(const a: BigInt; b: Int64): boolean;
class operator >=(a: Int64; const b: BigInt): boolean;
// formatting (negative values get a leading "-", also in hex/bin/oct)
function toString: string;
function toString(base: integer): string;
function toHex: string;
function toBin: string;
function toOct: string;
// numeric conversions (raise ERangeError when the value does not fit)
function toInt8: Int8;
function toUInt8: UInt8;
function toInt16: Int16;
function toUInt16: UInt16;
function toInt32: Int32;
function toUInt32: UInt32;
function toInt64: Int64;
function toUInt64: UInt64;
{$ifdef BIGINT_HAS_INT128}
function toInt128: Int128;
function toUInt128: UInt128;
{$endif}
function toDouble: Double;
function toUBigInt: UBigInt;
// does the value fit in each native integer width
function fitsInInt8: boolean;
function fitsInUInt8: boolean;
function fitsInInt16: boolean;
function fitsInUInt16: boolean;
function fitsInInt32: boolean;
function fitsInUInt32: boolean;
function fitsInInt64: boolean;
function fitsInUInt64: boolean;
{$ifdef BIGINT_HAS_INT128}
function fitsInInt128: boolean;
function fitsInUInt128: boolean;
{$endif}
// predicates
function isZero: boolean;
function isOne: boolean;
function isEven: boolean;
function isOdd: boolean;
function isNegative: boolean;
function isPositive: boolean;
function isPowerOfTwo: boolean;
function sign: integer;
// sign helpers
function abs: BigInt;
function magnitude: UBigInt;
procedure negate;
// bit access in two's complement (testBit of a negative sees infinite ones)
function bitLength: LongWord;
function popCount: LongWord;
function lowestSetBit: Int64;
function testBit(i: LongWord): boolean;
procedure setBit(i: LongWord);
procedure clearBit(i: LongWord);
procedure flipBit(i: LongWord);
property bits[i: LongWord]: boolean read getBitProp write putBitProp;
// comparison helpers
function compare(const other: BigInt): integer;
function equals(const other: BigInt): boolean;
// constant-time variants, see UBigInt
function equalsCT(const other: BigInt): boolean;
function compareCT(const other: BigInt): integer;
procedure secureClear;
function min(const other: BigInt): BigInt;
function max(const other: BigInt): BigInt;
// division helpers: divMod truncates (like div/mod), floor variants round
// toward -infinity (like Python), ceilDiv rounds toward +infinity
function divMod(const d: BigInt): (q, r: BigInt);
function floorDiv(const d: BigInt): BigInt;
function floorMod(const d: BigInt): BigInt;
function ceilDiv(const d: BigInt): BigInt;
// misc
procedure swap(var other: BigInt);
// parsing (sign plus the same prefixes and separators as UBigInt)
class function parse(const s: string): BigInt; static;
class function parse(const s: string; base: integer): BigInt; static;
class function tryParse(const s: string; out v: BigInt): boolean; static;
class function tryParse(const s: string; base: integer; out v: BigInt): boolean; static;
// math
function sqr: BigInt;
function sqrt: BigInt;
function nthRoot(n: LongWord): BigInt;
function pow(e: LongWord): BigInt;
// modPow: modulus must be positive, result in [0, m),
// a negative exponent goes through the modular inverse
function modPow(const e, m: BigInt): BigInt;
function modInverse(const m: BigInt): BigInt;
function gcd(const other: BigInt): BigInt;
function lcm(const other: BigInt): BigInt;
// extras: number theory (these all work on the absolute value)
function gcdExt(const other: BigInt): (g, x, y: BigInt);
function jacobi(const n: BigInt): integer;
function kronecker(const n: BigInt): integer;
function modSqrt(const p: BigInt): BigInt;
// one k-th root modulo an odd prime (Adleman-Manders-Miller); raises when
// none exists
function nthRootMod(k: LongWord; const p: BigInt): BigInt;
// least k > 0 with self^k = 1 (mod m); self must be coprime to m
function multiplicativeOrder(const m: BigInt): BigInt;
function isPrimitiveRoot(const m: BigInt): boolean;
// smallest primitive root modulo self (exists for 1, 2, 4, p^k, 2*p^k)
function primitiveRoot: BigInt;
function isPerfectSquare: boolean;
function sqrtRem: (root, rem: BigInt);
function factorize: array of (p: BigInt; e: LongWord);
function eulerPhi: BigInt;
function carmichaelLambda: BigInt;
function moebius: integer;
function sigma(k: LongWord = 1): BigInt;
function tau: BigInt;
function radical: BigInt;
function divisors: array of BigInt;
function isSquarefree: boolean;
function isPerfect: boolean;
function isCarmichael: boolean;
function isKthPower(k: LongWord): boolean;
// primes: negative values are never prime, nextPrime returns the first prime > self
function isProbablePrime(rounds: integer = 24): boolean;
function isPrime: boolean;
function nextPrime: BigInt;
function prevPrime: BigInt;
// bytes: minimal two's complement with sign bit, like Java toByteArray
function toBytesLE: TBytes;
function toBytesBE: TBytes;
// fixed width: sign-extended two's complement over len bytes (ERangeError
// when the value does not fit)
function toBytesLE(len: SizeInt): TBytes;
function toBytesBE(len: SizeInt): TBytes;
class function fromBytesLE(const bytes: TBytes): BigInt; static;
class function fromBytesBE(const bytes: TBytes): BigInt; static;
class function fromBytesLE(src: Pointer; len: SizeInt): BigInt; static;
class function fromBytesBE(src: Pointer; len: SizeInt): BigInt; static;
// two's complement bytes packed in a string container (raw bytes, not
// digit text)
function toByteStringLE: string;
function toByteStringBE: string;
class function fromByteStringLE(const s: string): BigInt; static;
class function fromByteStringBE(const s: string): BigInt; static;
// allocates dst with GetMem and fills it with the two's complement bytes;
// the caller must release it with FreeMem. returns the byte count
function toBytesLE(out dst: Pointer): SizeInt;
function toBytesBE(out dst: Pointer): SizeInt;
// misc
function digitCount: LongWord;
function toStringGrouped(sep: char = '_'; groupSize: integer = 3): string;
// number in Roman numerals (1..3999); in words (English short scale)
function toRoman: string;
function toWords: string;
function hashCode: DWord;
// constants and generators
class function zero: BigInt; static;
class function one: BigInt; static;
class function two: BigInt; static;
class function ten: BigInt; static;
class function minusOne: BigInt; static;
class function pow2(n: LongWord): BigInt; static;
class function random(bits: LongWord): BigInt; static;
class function randomBelow(const bound: BigInt): BigInt; static;
class function randomRange(const lo, hi: BigInt): BigInt; static;
class function randomPrime(bits: LongWord; rounds: integer = 24): BigInt; static;
// CSPRNG variants, see UBigInt
class function randomSecure(bits: LongWord): BigInt; static;
class function randomSecureBelow(const bound: BigInt): BigInt; static;
class function randomSecureRange(const lo, hi: BigInt): BigInt; static;
class function randomSecurePrime(bits: LongWord; rounds: integer = 24): BigInt; static;
// Chinese remainder theorem for pairwise coprime positive moduli
class function crt(const remainders, moduli: array of BigInt): BigInt; static;
// Lucas sequences U_n(P,Q), V_n(P,Q) modulo an odd m, by index doubling
class function lucasSequence(const p, q, n, m: BigInt): (u, v: BigInt); static;
class function factorial(n: LongWord): BigInt; static;
class function fibonacci(n: LongWord): BigInt; static;
class function lucas(n: LongWord): BigInt; static;
class function binomial(n, k: LongWord): BigInt; static;
// C(n, k) mod prime p for arbitrarily large n, k via the Lucas theorem
class function binomialMod(const n, k, p: BigInt): BigInt; static;
class function multinomial(const ks: array of LongWord): BigInt; static;
class function risingFactorial(const x: BigInt; n: LongWord): BigInt; static;
class function fallingFactorial(const x: BigInt; n: LongWord): BigInt; static;
class function catalan(n: LongWord): BigInt; static;
class function primorial(n: LongWord): BigInt; static;
class function subfactorial(n: LongWord): BigInt; static;
class function bell(n: LongWord): BigInt; static;
// signed Stirling numbers of the first kind, Stirling of the second kind
class function stirling1(n, k: LongWord): BigInt; static;
class function stirling2(n, k: LongWord): BigInt; static;
class function partitions(n: LongWord): BigInt; static;
// Bernoulli number as an exact reduced fraction (num/den)
class function bernoulli(n: LongWord): (num, den: BigInt); static;
// continued fractions: coefficients of num/den, and the rebuild to a
// reduced fraction
class function continuedFraction(const num, den: BigInt): array of BigInt; static;
class function fromContinuedFraction(const cf: array of BigInt): (num, den: BigInt); static;
end;
// rounding modes for BigDecimal.rounded: bdrRound rounds halves away from
// zero, bdrHalfUp rounds halves toward +infinity, bdrHalfEven to the even
// neighbor (banker's rounding)
TBigDecimalRounding = (bdrTrunc, bdrCeil, bdrFloor, bdrRound, bdrHalfUp, bdrHalfEven);
{ BigDecimal - arbitrary precision decimal float: value = mantissa * 10^exp
with a BigInt mantissa, kept canonical (no trailing zero digits).
+ - * are exact; / rounds to a chosen number of fractional digits and
keeps one hidden guard digit, so (1/3)*3 still prints as 1 }
BigDecimal = record
private
fMan: BigInt; // decimal mantissa
fExp: integer; // value = fMan * 10^fExp
fHidden: boolean; // last mantissa digit is a division guard, hidden by toString
public
// conversions in
class operator :=(x: Int64): BigDecimal;
class operator :=(x: QWord): BigDecimal;
class operator :=(const s: string): BigDecimal;
class operator :=(const a: BigInt): BigDecimal;
class operator :=(const a: UBigInt): BigDecimal;
// float casts take the shortest decimal that reads back to the same
// float (0.1 gives 0.1); fromDoubleExact gives the exact binary value
class operator explicit(d: Double): BigDecimal;
class operator explicit(s: Single): BigDecimal;
// exact integer paths for typecasts, so BigDecimal(q) never rounds via Double
class operator explicit(x: Int64): BigDecimal;
class operator explicit(x: QWord): BigDecimal;
// conversions out (the BigInt cast raises ERangeError unless integral)
class operator explicit(const a: BigDecimal): Double;
class operator explicit(const a: BigDecimal): Single;
class operator explicit(const a: BigDecimal): string;
class operator explicit(const a: BigDecimal): BigInt;
// arithmetic: + - * are exact, / rounds to 18 fractional digits (see
// divide), div/mod are the integer quotient and the exact remainder
class operator +(const a, b: BigDecimal): BigDecimal;
class operator -(const a, b: BigDecimal): BigDecimal;
class operator *(const a, b: BigDecimal): BigDecimal;
class operator /(const a, b: BigDecimal): BigDecimal;
class operator div(const a, b: BigDecimal): BigDecimal;
class operator mod(const a, b: BigDecimal): BigDecimal;
class operator **(const a: BigDecimal; e: Int64): BigDecimal;
class operator **(const a, b: BigDecimal): BigDecimal;
class operator inc(const a: BigDecimal): BigDecimal;
class operator dec(const a: BigDecimal): BigDecimal;
// unary
class operator -(const a: BigDecimal): BigDecimal;
class operator +(const a: BigDecimal): BigDecimal;
// comparisons (numeric: 0.5 = 5E-1 whatever the representation)
class operator =(const a, b: BigDecimal): boolean;
class operator <>(const a, b: BigDecimal): boolean;
class operator <(const a, b: BigDecimal): boolean;
class operator <=(const a, b: BigDecimal): boolean;
class operator >(const a, b: BigDecimal): boolean;
class operator >=(const a, b: BigDecimal): boolean;
// formatting: toString is plain decimal (-123.45), toScientific keeps
// one leading digit (-1.2345E2), toEngineering an exponent that is a
// multiple of three (-123.45E0, 12.5E3)
function toString: string;
function toScientific: string;
function toEngineering: string;
// exact conversions (raise ERangeError unless integral and in range;
// use trunc/floor/ceil/round for the lossy ones)
function toInt8: Int8;
function toUInt8: UInt8;
function toInt16: Int16;
function toUInt16: UInt16;
function toInt32: Int32;
function toUInt32: UInt32;
function toInt64: Int64;
function toUInt64: UInt64;
{$ifdef BIGINT_HAS_INT128}
function toInt128: Int128;
function toUInt128: UInt128;
{$endif}
function toBigInt: BigInt;
function toUBigInt: UBigInt;
// integral and inside each native integer width
function fitsInInt8: boolean;
function fitsInUInt8: boolean;
function fitsInInt16: boolean;
function fitsInUInt16: boolean;
function fitsInInt32: boolean;
function fitsInUInt32: boolean;
function fitsInInt64: boolean;
function fitsInUInt64: boolean;
{$ifdef BIGINT_HAS_INT128}
function fitsInInt128: boolean;
function fitsInUInt128: boolean;
{$endif}
// correctly rounded to the nearest float (ties to even); overflow gives
// infinity, underflow gives zero
function toDouble: Double;
function toSingle: Single;
{$ifdef FPC_HAS_TYPE_EXTENDED}
function toExtended: Extended;
{$endif}
// predicates
function isZero: boolean;
function isOne: boolean;
function isIntegral: boolean;
// parity of integral values; a fractional value is neither even nor odd
function isEven: boolean;
function isOdd: boolean;
function isNegative: boolean;
function isPositive: boolean;
function sign: integer;
// sign helpers
function abs: BigDecimal;
procedure negate;
// integer parts: trunc cuts toward zero, floor toward -infinity, ceil
// toward +infinity, round takes halves to even (like Pascal round);
// frac is what trunc drops, so self = trunc + frac
function trunc: BigInt;
function floor: BigInt;
function ceil: BigInt;
function round: BigInt;
function frac: BigDecimal;
// exact rational view: self = num / den with a reduced power-of-ten
// denominator, so 0.375 gives (3, 8)
function toFraction: (num, den: BigInt);
// continued fraction coefficients of the exact value (maxTerms <= 0 for
// all of them); great for best rational approximations
function continuedFraction(maxTerms: integer = 0): array of BigInt;
// decimal introspection: precision counts significant digits, getDigit
// returns the digit at 10^i of the absolute value (0 outside)
function precision: integer;
function mostSignificantExponent: integer;
function getDigit(i: integer): integer;
// multiply by a power of ten
procedure shift10(n: integer);
function shifted10(n: integer): BigDecimal;
// round to a decimal position: toDigit 0 = integer, -2 = cents, 3 = thousands
function rounded(toDigit: integer = 0; mode: TBigDecimalRounding = bdrRound): BigDecimal;
// round to the nearest multiple of an arbitrary step, e.g. 0.05
function quantize(const step: BigDecimal; mode: TBigDecimalRounding = bdrRound): BigDecimal;
// comparison helpers
function compare(const other: BigDecimal): integer;
function equals(const other: BigDecimal): boolean;
function approxEquals(const other, epsilon: BigDecimal): boolean;
function min(const other: BigDecimal): BigDecimal;
function max(const other: BigDecimal): BigDecimal;
// division: the quotient carries `precision` fractional digits (more when
// the operands are finer, always the full integer part) plus a hidden
// guard digit; exact quotients stay exact. divMod gives the integer
// quotient and the exact remainder
function divide(const other: BigDecimal; precision: integer = 18): BigDecimal;
function divMod(const d: BigDecimal): (q, r: BigDecimal);
// parsing: [sign]digits[.digits][E[sign]digits], "_" separators allowed
class function parse(const s: string): BigDecimal; static;
class function tryParse(const s: string; out v: BigDecimal): boolean; static;
// calculator: evaluate a textual expression at the given precision, e.g.
// calc('2^100 / sqrt(2)'). Operators + - * / div mod(%) ^(**) !, the
// usual precedence with a right-associative power; functions sqrt cbrt
// root pow sqr abs sign frac exp ln log log2 log10 logb sin cos tan asin
// acos atan sinh cosh tanh asinh acosh atanh floor ceil round trunc gamma
// lngamma erf erfc factorial min max gcd lcm atan2 hypot agm; constants pi
// e tau phi. Stateless:
// no variables, syntax errors raise EConvertError with the position
class function calc(const s: string; precision: integer = 18): BigDecimal; static;
class function tryCalc(const s: string; out v: BigDecimal; precision: integer = 18): boolean; static;
// math: sqrt keeps `precision` fractional digits plus the same hidden
// guard digit as divide; pow with a negative exponent divides at the
// default precision; gcd/lcm work on the decimal lattice, so
// gcd(0.25, 0.15) = 0.05
function sqrt(precision: integer = 18): BigDecimal;
function pow(e: Int64): BigDecimal;
function pow(const y: BigDecimal; precision: integer = 18): BigDecimal;
function nthRoot(n: LongWord; precision: integer = 18): BigDecimal;
function gcd(const other: BigDecimal): BigDecimal;
function lcm(const other: BigDecimal): BigDecimal;
// transcendentals: `precision` fractional digits (and at least that many
// significant digits for tiny results) behind the same hidden guard
// digit as divide; computed over scaled integers with extra working
// digits. log10 is exact for powers of ten, log2 for powers of two,
// a fractional pow goes through exp(y * ln x)
function exp(precision: integer = 18): BigDecimal;
function ln(precision: integer = 18): BigDecimal;
function log2(precision: integer = 18): BigDecimal;
function log10(precision: integer = 18): BigDecimal;
function logBase(const b: BigDecimal; precision: integer = 18): BigDecimal;
// trigonometry in radians; large arguments are reduced modulo pi/2 with
// pi carried at a matching precision, arcsin/arccos raise EBigIntError
// outside -1..1
function sin(precision: integer = 18): BigDecimal;
function cos(precision: integer = 18): BigDecimal;
function tan(precision: integer = 18): BigDecimal;
function arcsin(precision: integer = 18): BigDecimal;
function arccos(precision: integer = 18): BigDecimal;
function arctan(precision: integer = 18): BigDecimal;
// hyperbolics
function sinh(precision: integer = 18): BigDecimal;
function cosh(precision: integer = 18): BigDecimal;
function tanh(precision: integer = 18): BigDecimal;
// inverse hyperbolics; arccosh needs x >= 1, arctanh needs -1 < x < 1
function arcsinh(precision: integer = 18): BigDecimal;
function arccosh(precision: integer = 18): BigDecimal;
function arctanh(precision: integer = 18): BigDecimal;
// special functions: the gamma function and its logarithm (positive
// argument for lnGamma, reflection covers negatives for gamma), the real
// factorial x! = gamma(x+1), the error function and its complement
function lnGamma(precision: integer = 18): BigDecimal;
function gamma(precision: integer = 18): BigDecimal;
function factorial(precision: integer = 18): BigDecimal;
function erf(precision: integer = 18): BigDecimal;
function erfc(precision: integer = 18): BigDecimal;
// round to a count of significant digits rather than a decimal position
function roundToSignificant(digits: integer; mode: TBigDecimalRounding = bdrRound): BigDecimal;
// float builders: plain takes the shortest round-tripping decimal,
// exact the full binary expansion
class function fromDouble(d: Double): BigDecimal; static;
class function fromDoubleExact(d: Double): BigDecimal; static;
class function fromSingle(s: Single): BigDecimal; static;
class function fromSingleExact(s: Single): BigDecimal; static;
{$ifdef FPC_HAS_TYPE_EXTENDED}
class function fromExtended(e: Extended): BigDecimal; static;
class function fromExtendedExact(e: Extended): BigDecimal; static;
{$endif}
// misc
function hashCode: DWord;
procedure swap(var other: BigDecimal);
// constants
class function zero: BigDecimal; static;
class function one: BigDecimal; static;
class function two: BigDecimal; static;
class function ten: BigDecimal; static;
// famous constants at any precision (pi is cached, Chudnovsky splitting)
class function pi(precision: integer = 18): BigDecimal; static;
class function e(precision: integer = 18): BigDecimal; static;
// two-argument arctangent (quadrant-aware), Euclidean length, and the
// arithmetic-geometric mean
class function atan2(const y, x: BigDecimal; precision: integer = 18): BigDecimal; static;
class function hypot(const x, y: BigDecimal; precision: integer = 18): BigDecimal; static;
class function agm(const a, b: BigDecimal; precision: integer = 18): BigDecimal; static;
end;
{ BigRational - exact arbitrary precision fraction }
// always normalized: den > 0, gcd(num, den) = 1, zero is 0/1; a
// default-initialized value reads as 0
BigRational = record
private
fNum, fDen: BigInt;
// fDen = 0 only in a default() blob, semantically 1
function getDen: BigInt; inline;
procedure normalize;
public
class operator Initialize(var x: BigRational);
class operator :=(x: Int64): BigRational;
class operator :=(const s: string): BigRational;
class operator :=(const a: BigInt): BigRational;
class operator :=(const a: UBigInt): BigRational;
// exact value of the double (5.1 parses as the fraction 51/10, but a
// Double cast converts the actual binary value)
class operator explicit(d: Double): BigRational;
class operator explicit(const a: BigRational): Double;
class operator explicit(const a: BigRational): string;
// truncates toward zero
class operator explicit(const a: BigRational): BigInt;
class operator +(const a, b: BigRational): BigRational;
class operator -(const a, b: BigRational): BigRational;
class operator *(const a, b: BigRational): BigRational;
class operator /(const a, b: BigRational): BigRational;
class operator **(const a: BigRational; e: Int64): BigRational;
class operator -(const a: BigRational): BigRational;
class operator +(const a: BigRational): BigRational;
class operator =(const a, b: BigRational): boolean;
class operator <>(const a, b: BigRational): boolean;
class operator <(const a, b: BigRational): boolean;
class operator <=(const a, b: BigRational): boolean;
class operator >(const a, b: BigRational): boolean;
class operator >=(const a, b: BigRational): boolean;
// components (den is always positive)
function num: BigInt;
function den: BigInt;
class function create(const num, den: BigInt): BigRational; static;
// accepts 'a/b', integers, decimals and exponents ('1.25', '2e10')
class function parse(const s: string): BigRational; static;
class function tryParse(const s: string; out v: BigRational): boolean; static;
// 'num/den', or just 'num' for integral values
function toString: string;
function toDecimal(precision: integer = 18): BigDecimal;
function toDouble: Double;
function isZero: boolean;
function isOne: boolean;
function isInteger: boolean;
function isNegative: boolean;
function isPositive: boolean;
function sign: integer;
function abs: BigRational;
procedure negate;
function reciprocal: BigRational;
function trunc: BigInt;
function floor: BigInt;
function ceil: BigInt;
function round: BigInt;
function frac: BigRational;
function pow(e: Int64): BigRational;
function compare(const other: BigRational): integer;
function equals(const other: BigRational): boolean;
function min(const other: BigRational): BigRational;
function max(const other: BigRational): BigRational;
function hashCode: DWord;
procedure swap(var other: BigRational);
// continued fraction expansion and the tightest fraction with a bounded
// denominator (best rational approximation via convergents)
function continuedFraction: array of BigInt;
class function fromContinuedFraction(const cf: array of BigInt): BigRational; static;
function limitDenominator(const maxDen: BigInt): BigRational;
class function zero: BigRational; static;
class function one: BigRational; static;
end;
{ TModRing - Montgomery multiplication context over a fixed odd modulus }
// precomputes the Montgomery constants once, then repeated modular products
// cost a single REDC pass each instead of a full division (RSA/ECC-style
// workloads: many multiplications against one modulus). values in the
// Montgomery domain are ordinary UBigInts below m carrying a*R mod m; the
// context keeps a scratch buffer, so share one ring per thread, not across
TModRing = record
private
fM: TBigIntLimbs;
fMU: UBigInt;
fN: SizeInt;
fMInv: TBigIntLimb;
fRR: TBigIntLimbs;
fOne: TBigIntLimbs;
fT: TBigIntLimbs;
function mulLimbs(const a, b: TBigIntLimbs): UBigInt;
public
class function create(const m: UBigInt): TModRing; static;
function modulus: UBigInt;
// Montgomery domain conversions
function toMont(const a: UBigInt): UBigInt;
function fromMont(const a: UBigInt): UBigInt;
// product/square of Montgomery-domain values
function mul(const a, b: UBigInt): UBigInt;
function sqr(const a: UBigInt): UBigInt;
// plain-domain helpers on the fixed modulus; add/sub expect reduced
// operands (below m) and work in either domain
function add(const a, b: UBigInt): UBigInt;
function sub(const a, b: UBigInt): UBigInt;
function pow(const a, e: UBigInt): UBigInt;
function inv(const a: UBigInt): UBigInt;
function reduce(const a: UBigInt): UBigInt;
end;