Help with extremely large integer arithmetic

General
1

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 4x3x3+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!

2

If you have more RAM available than 1GB, can increase the stack memory allocated using e.g.:

:- set_prolog_flag(stack_limit, 3_647_483_648).

… at the top of the program code.

3

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.

4

Writing to only a text file should be more efficient than writing to the terminal.

E.g. I use sakura, and it can get slow when scrolling upwards through pages of output in its history buffer.

5

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.

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 :slight_smile:

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.

6

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.

7

Thanks. The results get written to a text file already. Calculating them is the issue!

8

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:

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.

9

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.

10

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.

11

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.

12

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

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, <compound (^)/2>)
ERROR:     [13] '$toplevel':toplevel_call(<compound (:)/2>)
ERROR:     [12] '$toplevel':stop_backtrace(<compound (:)/2>, _67111638)
ERROR:     [11] '$tabling':'$wfs_call'(<compound (:)/2>, <compound (:)/2>)
ERROR:     [9] '$toplevel':'$execute_goal2'(<compound (:)/2>, [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.

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, <compound (^)/2>)
ERROR:     [13] '$toplevel':toplevel_call(<compound (:)/2>)
ERROR:     [12] '$toplevel':stop_backtrace(<compound (:)/2>, _2382)
ERROR:     [11] '$tabling':'$wfs_call'(<compound (:)/2>, <compound (:)/2>)
ERROR:     [9] '$toplevel':'$execute_goal2'(<compound (:)/2>, [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.

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, <compound (^)/2>)
ERROR:     [13] '$toplevel':toplevel_call(<compound (:)/2>)
ERROR:     [12] '$toplevel':stop_backtrace(<compound (:)/2>, _11602)
ERROR:     [11] '$tabling':'$wfs_call'(<compound (:)/2>, <compound (:)/2>)
ERROR:     [9] '$toplevel':'$execute_goal2'(<compound (:)/2>, [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 …

13

Ah, Windows long is 32 bits :frowning: 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.

14

Thanks! Much appreciated.