# Help with extremely large integer arithmetic **URL:** \ **Category:** General\ **Created:** [July 31, 2026, 3:33pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768 "2026-07-31T15:33:12Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [July 31, 2026, 3:33pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/1 "2026-07-31T15:33:12Z")
G’day all. For reasons that rhyme with “busy beaver”, I have been using SWI-Prolog for evaluating expressions that can involve integers which are tens of thousands of digits long. So far, with the largest expression evaluating to something a number with 40,000 digits, so good. The infinite precision integer arithmetic in SWI-Prolog works very well for this. However, recently I have had cause to (attempt to) evaluate the expression 2 to the power of 2X-1 where X is a 33-digit number (plus some significantly smaller expressions). Doing the obvious (but naive) thing of using ‘is’ causes a stack overflow, as it takes more than 1Gb to write this out! Roughly speaking, it seems integers up to about 2 to the power of 10 million are evaluable, but beyond that memory capacity limits explicit calculation. So it seems the only solution is to use some kind of “lazier” evaluation, in which the exponentials are left unevaluated, but the unproblematic parts (eg 4_x_3x3+1363+1156) are made explicit. Does anyone have any pointers on such lazy (semi-symbolic) evaluation? Any tips or pointers would be greatly appreciated. Echoing some of Jan’s comments on Claude code, I suspect will have to get into agentic code generation by necessity, and probably end up using some symbolic algebra libraries (like Maple or Mathematica). Doing the coding to generate the expression mentioned above was hairy enough! ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [July 31, 2026, 4:41pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/2 "2026-07-31T16:41:19Z")
> [@PlacidPlatypus](#): > > stack overflow, as it takes more than 1Gb If you have more RAM available than 1GB, can increase the stack memory allocated using e.g.: ```prolog :- set_prolog_flag(stack_limit, 3_647_483_648). ``` … at the top of the program code. ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 1, 2026, 12:25am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/3 "2026-08-01T00:25:19Z")
Thanks. I have 32G of RAM on my PC, so I could increase the stack size. But I suspect that will only postpone the problem rather than solve it. ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [August 1, 2026, 7:04am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/4 "2026-08-01T07:04:34Z")
> [@PlacidPlatypus](#): > > it takes more than 1Gb to write this out! Writing to only a text file should be more efficient than writing to the terminal. E.g. I use [sakura](https://github.com/dabisu/sakura), and it can get slow when scrolling upwards through pages of output in its history buffer. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [August 1, 2026, 8:01am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/5 "2026-08-01T08:01:24Z")
> [@PlacidPlatypus](#): > > as it takes more than 1Gb to write this out! You can use portray/1 to avoid writing these big integers. The toplevel and debugger and almost all messages use print/1 (or format/2 `~p`) to print values. > [@PlacidPlatypus](#): > > Does anyone have any pointers on such lazy (semi-symbolic) evaluation? Any tips or pointers would be greatly appreciated. Maybe you could keep intermediate exponential expressions as terms (X^Y), delaying their evaluation as long as possible and (hopefully) reformulate the expression such that huge intermediate results are minimized. Symbolic rewriting of expressions is surely something Prolog is good at 🙂 And, as said, raise the stack limit. Also avoid unneeded choicepoints as they (may) keep huge numbers accessible and thus reduce the effectiveness of GC. ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 1, 2026, 10:28am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/6 "2026-08-01T10:28:35Z")
Thanks. Writing the large numbers out is not the biggest issue but that will.be helpful. I am already doing a lot of term rewriting at the moment and this feels like another level. As you said, Prolog is a good choice for this. Increasing the stack will help of course but I suspect it may not help a lot. ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 1, 2026, 10:29am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/7 "2026-08-01T10:29:35Z")
Thanks. The results get written to a text file already. Calculating them is the issue! ---
**Author:** ![kwon-young](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/kwon-young/32/4841_2.png) [@kwon-young](https://swi-prolog.discourse.group/u/kwon-young)\ **Post date:** [August 1, 2026, 3:04pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/8 "2026-08-01T15:04:07Z")
Hello, My advice would be to just implement an overloaded `is` predicate that would pattern match exponential and keep them unevaluated. you just need to formalize the data structure that you will use to represent your numbers. Let’s say I use `eval` as my overloaded `is` functor: ```prolog eval(A^B*A^D, R) => eval(A, A1), eval(B, B1), eval(D, D1), eval(B+D, BD), R = A^BD. eval(A, R) => % delegate the rest to `is` R is A. ``` This is just an advice, I am not sure it will work for your case. But this is how I implemented my own unit aware arithmetic evaluation predicate. Note the use of `=>` SSU predicates which are extremely useful for this kind of 1 way pattern matching. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [August 1, 2026, 4:11pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/9 "2026-08-01T16:11:24Z")
> [@kwon-young](#): > > ```prolog > eval(A^B*A^D, R) => > eval(A, A1), eval(B, B1), eval(D, D1), > eval(B+D, BD), > R = A^BD. > > ``` Ideally (for SWI-Prolog) you rewrite the expression to a new expression and evaluate that using a single is/2 call. The reason for this is that this avoids repeated copying of results between GMP allocated numbers and the Prolog stacks. I.e., GMP numbers on the Prolog stacks can be used as read-only numbers by GMP. Evaluating requires writeable numbers and these are allocated by GMP. Intermediate results remain managed by GMP. Once the evaluation of is/2 finishes the result is copied to the Prolog stack (and all intermediates are deleted). This all does not matter to much with typical small numbers. It does matter with huge numbers though. ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 2, 2026, 2:46am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/10 "2026-08-02T02:46:03Z")
Thanks. Something like that sounds sensible. I already have my own predicate `simplify_expression` which applies to expressions involving variables as well, so that terms like `1+X+2+X ` are evaluated to `2*X+1` . The first clause of this is (more or less) as below. `simplify_expression(Exp, Term) :- ground(Exp), !, Term is Exp.` Expanding this to more cases should, in principle, be simple enough. ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 2, 2026, 2:50am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/11 "2026-08-02T02:50:06Z")
Thanks for the tip. Sounds like that will be useful when dealing with these. I am also increasingly thinking that this is going to be a matter of smoothly transitioning from explicit evaluation to use of Knuth’s up arrow notation or similar variants. ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 3, 2026, 12:53pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/12 "2026-08-03T12:53:14Z")
Been experimenting with the stack size, and I thought others may be interested in the results below. It seems 2^2147483647 is evaluable with a 1Gb stack, but 2^2147483648 is not. But note the third query below ```prolog 123 ?- N = 2147483647, _ is 2^N. N = 2147483647. 124 ?- N = 2147483648, _ is 2^N. ERROR: Stack limit (1.0Gb) exceeded ERROR: Stack sizes: local: 2Kb, global: 0.3Gb, trail: 0Kb ERROR: Stack depth: 15, last-call: 27%, Choice points: 6 ERROR: In: ERROR: [15] system:is(_67111586, ) ERROR: [13] '$toplevel':toplevel_call() ERROR: [12] '$toplevel':stop_backtrace(, _67111638) ERROR: [11] '$tabling':'$wfs_call'(, ) ERROR: [9] '$toplevel':'$execute_goal2'(, [length:1], true) ERROR: ERROR: Use the --stack_limit=size[KMG] command line option or ERROR: ?- set_prolog_flag(stack_limit, 2_147_483_648). to double the limit. 125 ?- N = 2147483648//2, _ is 2^N * 2^N. N = 2147483648//2. ``` Also increasing the stack size (at least in the obvious way) doesn’t seem to help. ```prolog 126 ?- set_prolog_flag(stack_limit, 2_147_483_648). true. 127 ?- N = 2147483648, _ is 2^N. ERROR: Stack limit (2.0Gb) exceeded ERROR: Stack sizes: local: 2Kb, global: 8Kb, trail: 0Kb ERROR: Stack depth: 15, last-call: 27%, Choice points: 6 ERROR: In: ERROR: [15] system:is(_2330, ) ERROR: [13] '$toplevel':toplevel_call() ERROR: [12] '$toplevel':stop_backtrace(, _2382) ERROR: [11] '$tabling':'$wfs_call'(, ) ERROR: [9] '$toplevel':'$execute_goal2'(, [length:1], true) ERROR: ERROR: Use the --stack_limit=size[KMG] command line option or ERROR: ?- set_prolog_flag(stack_limit, 4_294_967_296). to double the limit. ``` ```prolog 128 ?- set_prolog_flag(stack_limit, 4_294_967_296). true. 129 ?- N = 2147483648, _ is 2^N. ERROR: Stack limit (4.0Gb) exceeded ERROR: Stack sizes: local: 2Kb, global: 44Kb, trail: 0Kb ERROR: Stack depth: 15, last-call: 27%, Choice points: 6 ERROR: In: ERROR: [15] system:is(_11550, ) ERROR: [13] '$toplevel':toplevel_call() ERROR: [12] '$toplevel':stop_backtrace(, _11602) ERROR: [11] '$tabling':'$wfs_call'(, ) ERROR: [9] '$toplevel':'$execute_goal2'(, [length:1], true) ERROR: ERROR: Use the --stack_limit=size[KMG] command line option or ERROR: ?- set_prolog_flag(stack_limit, 8_589_934_592). to double the limit. ``` So roll on lazy exponential evaluation … ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [August 3, 2026, 2:25pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/13 "2026-08-03T14:25:34Z")
> [@PlacidPlatypus](#): > > It seems 2^2147483647 is evaluable with a 1Gb stack, but 2^2147483648 is not. But note the third query below Ah, Windows `long` is 32 bits ☹ The code assumed that `2^LONG_MAX` surely is a stack overflow, but that is not true on 64 bit Windows. Works fine on non-Windows. Pushed a fix that makes this work on Windows as well. Should be in tomorrows daily build. ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 3, 2026, 10:27pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/14 "2026-08-03T22:27:36Z")
Thanks! Much appreciated. ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 28, 2026, 9:11am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/15 "2026-08-28T09:11:21Z")
Just noticed something rather inexplicable to me when playing around with some lazy evaluation as on this thread. The first query below works fine. The second one crashes the system (I am using 10.1.13-1 on Windows). ```prolog B = 2147483648, Z = 4^B, C is B+B, _ is 2^C. % succeeds B = 2147483647, Z = 4^B, C is B+B, _ is 2^C. % crashes everything! ``` From what I observe any value of B in the range 2147383488 to 2147483647 include will behave this way, but numbers outside this range (including many much larger) work fine. It has not escaped my attention that this range is 2^31-161 to 2^31 -1 inclusive, but I am not sure why that would be the case. I have not yet tried going back to the last stable release (10.0.2-1) or the latest daily build, but I guess those are the next obvious things to try. Any tips would be gratefully received. ---
**Author:** ![brebs](https://avatars.discourse-cdn.com/v4/letter/b/e9c0ed/32.png) [@brebs](https://swi-prolog.discourse.group/u/brebs)\ **Post date:** [August 28, 2026, 11:33am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/16 "2026-08-28T11:33:13Z")
> [@PlacidPlatypus](#): > > `% crashes everything!` Works on Linux (distro is Void Linux): ```prolog Welcome to SWI-Prolog (threaded, 64 bits, version 10.0.2) 101 ?- B = 2147483647, Z = 4^B, C is B+B, _ is 2^C. B = 2147483647, Z = 4^2147483647, C = 4294967294. ``` ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 28, 2026, 11:54am UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/17 "2026-08-28T11:54:54Z")
Thanks. I am jealous! ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [August 28, 2026, 12:04pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/18 "2026-08-28T12:04:05Z")
It works on anything but Windows, which is the only 64 bit architecture I’m aware of where the C type `long` is 32 bits. Long is used in many of the libGMP API calls as well as internally. I have a patch, but need some more testing before calling victory. Bottom line will be that big integers on Windows cannot exceed 512Mb storage. There are two ways out: use LibBF rather than libGMP (but libBF is considerably slower on many operations) or use something else than Windows. Using WSL you should be able to run the Linux version. I have no intend to move the Windows releases to libBF as I think the performance matters to more users, but you can build it that way from source. ---
**Author:** ![PlacidPlatypus](https://avatars.discourse-cdn.com/v4/letter/p/5f8ce5/32.png) [@PlacidPlatypus](https://swi-prolog.discourse.group/u/PlacidPlatypus)\ **Post date:** [August 28, 2026, 12:25pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/19 "2026-08-28T12:25:56Z")
Thanks Jan. I think the best way forward will be to limit evaluation to integers under 2^31. There needs to be a limit anyway and If this is a little more conservative then strictly necessary then so be it. ---
**Author:** ![jan](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/jan/32/4_2.png) [@jan](https://swi-prolog.discourse.group/u/jan)\ **Post date:** [August 28, 2026, 3:39pm UTC](https://swi-prolog.discourse.group/t/help-with-extremely-large-integer-arithmetic/9768/20 "2026-08-28T15:39:54Z")
> [@PlacidPlatypus](#): > > I think the best way forward will be to limit evaluation to integers under 2^31 I think the limit is 2^32-1 on Windows and memory on anything else.