The bignum bug(s)

simon commented

2026-02-27 02:37:16 +00:00

Owner

At some point in development I had bignums of two cells more or less working, but I've never had bignums of three cells working. Part of the problem here is I don't really understand C well enough to know exactly what's going on, and I don't have good enough debugging tools (or am not using them well enough) to see what's going on.

simon added the

bug

help wanted

labels 2026-02-27 02:37:25 +00:00

simon commented

2026-02-27 02:51:02 +00:00

Author

Owner

The following scratchpad shows that at one point we were getting past the first bignum barrier, but even this no longer works.

(set! i
  (+
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000))

(set! j (+ i i i i i i i i i i))

(set! k (+ j j j j j j j j j j))

(set! l (+ k k k k k k k k k k))

(set! m (+ l l l l l l l l l l))

(set! n (+ m m m m m m m m m m))

(set! o (+ n n n n n n n n n n))

(set! p (+ o o o o o o o o o o))

(set! q (+ p p p p p p p p p p))

(set! r (+ q q q q q q q q q q))

(set! s (+ r r r r r r r r r r))

(set! t (+ s s s s s s s s s s))

(set! u (+ t t t t t t t t t t))

(set! v (+ u u u u u u u u u u))

(set! x (+ v v v v v v v v v v))

(set! y (+ x x x x x x x x x x))

"we're OK to here: 10^36, which is below the 2^120 barrier so represented as two cells"
(inspect (set! z (+ y y y y y y y y y y)))

"This blows up: 10^37, which is a three cell bignum."
(inspect (set! final (+ z z z z z z z z z z)))

The following scratchpad shows that at one point we were getting past the first bignum barrier, but even this no longer works. ```lisp (set! i (+ 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000)) (set! j (+ i i i i i i i i i i)) (set! k (+ j j j j j j j j j j)) (set! l (+ k k k k k k k k k k)) (set! m (+ l l l l l l l l l l)) (set! n (+ m m m m m m m m m m)) (set! o (+ n n n n n n n n n n)) (set! p (+ o o o o o o o o o o)) (set! q (+ p p p p p p p p p p)) (set! r (+ q q q q q q q q q q)) (set! s (+ r r r r r r r r r r)) (set! t (+ s s s s s s s s s s)) (set! u (+ t t t t t t t t t t)) (set! v (+ u u u u u u u u u u)) (set! x (+ v v v v v v v v v v)) (set! y (+ x x x x x x x x x x)) "we're OK to here: 10^36, which is below the 2^120 barrier so represented as two cells" (inspect (set! z (+ y y y y y y y y y y))) "This blows up: 10^37, which is a three cell bignum." (inspect (set! final (+ z z z z z z z z z z))) ```

simon commented

2026-02-27 03:17:39 +00:00

Author

Owner

The system can manage integers up to beyond +- 1,000,000,000,000,000,000 (10¹⁸), and although I really want bignums to work, that's probably good enough for now.

The system can manage integers up to beyond +- 1,000,000,000,000,000,000 (10<sup>18</sup>), and although I really want bignums to work, that's probably good enough for now.

simon commented

2026-02-27 03:23:00 +00:00

Author

Owner

In the 0.0.5 build, we are managing numbers just across the bignum boundary:

:: 1152921504606846977

1,152,921,504,606,846,977
:: (inspect 1152921504606846977)

        INTR (1381256777) at page 5, offset 803 count 2
                Integer cell: value 1, count 2
                BIGNUM! More at:
        INTR (1381256777) at page 5, offset 802 count 1
                Integer cell: value 1, count 1

We can even add numbers to them, for small values of numbers.

:: (+ 1152921504606846977 1)

1,152,921,504,606,846,978

:: (inspect (+ 1152921504606846977 1))

        INTR (1381256777) at page 5, offset 469 count 1
                Integer cell: value 2, count 1
                BIGNUM! More at:
        INTR (1381256777) at page 5, offset 468 count 1
                Integer cell: value 1, count 1

if we consider that 2⁶⁰ (1,152,921,504,606,846,976) is, to our bignum system, the equivalent of 10 to the decimal system, then 1,152,921,504,606,846,977 is the equivalent of 11, and, as we see from the inspector above, 1,152,921,504,606,846,978 is the equivalent of 12. I can add 1,152,921,504,606,846,975 — the equivalent of 9 — to itself and get a valid number:

:: (+ 1152921504606846975 1152921504606846975)

2,305,843,009,213,693,950

:: (inspect (+ 1152921504606846975 1152921504606846975))

        INTR (1381256777) at page 3, offset 452 count 1
                Integer cell: value 1152921504606846974, count 1
                BIGNUM! More at:
        INTR (1381256777) at page 3, offset 451 count 1
                Integer cell: value 1, count 1

That's the equivalent of 18 on this analogy, and you can see that the first digit is 1, and the second 'digit' is two less than the equivalent of 10, so that this is correct. But when I try to multiply 1152921504606846975 by 1152921504606846975, the equivalent of 81 to pursue the analogy,

Further exploration is needed to find exactly where it does break down. But we have got a regression, because the pre-release build for 0.0.6 can't even do this.

In the 0.0.5 build, we are managing numbers **just** across the bignum boundary: ```lisp :: 1152921504606846977 1,152,921,504,606,846,977 :: (inspect 1152921504606846977) INTR (1381256777) at page 5, offset 803 count 2 Integer cell: value 1, count 2 BIGNUM! More at: INTR (1381256777) at page 5, offset 802 count 1 Integer cell: value 1, count 1 ``` We can even add numbers to them, for small values of numbers. ```lisp :: (+ 1152921504606846977 1) 1,152,921,504,606,846,978 :: (inspect (+ 1152921504606846977 1)) INTR (1381256777) at page 5, offset 469 count 1 Integer cell: value 2, count 1 BIGNUM! More at: INTR (1381256777) at page 5, offset 468 count 1 Integer cell: value 1, count 1 ``` if we consider that 2<sup>60</sup> (1,152,921,504,606,846,976) is, to our bignum system, the equivalent of 10 to the decimal system, then 1,152,921,504,606,846,977 is the equivalent of 11, and, as we see from the inspector above, 1,152,921,504,606,846,978 is the equivalent of 12. I can add 1,152,921,504,606,846,975 — the equivalent of 9 — to itself and get a valid number: ```lisp :: (+ 1152921504606846975 1152921504606846975) 2,305,843,009,213,693,950 :: (inspect (+ 1152921504606846975 1152921504606846975)) INTR (1381256777) at page 3, offset 452 count 1 Integer cell: value 1152921504606846974, count 1 BIGNUM! More at: INTR (1381256777) at page 3, offset 451 count 1 Integer cell: value 1, count 1 ``` That's the equivalent of 18 on this analogy, and you can see that the first digit is 1, and the second 'digit' is two less than the equivalent of 10, so that this is correct. But when I try to multiply 1152921504606846975 by 1152921504606846975, the equivalent of 81 to pursue the analogy, Further exploration is needed to find exactly where it does break down. But we have got a regression, because the pre-release build for 0.0.6 can't even do this.

simon commented

2026-02-27 09:48:18 +00:00

Author

Owner

Last night's (or rather, very early this morning's) investigations showed that
version 0.0.5's bignum arithmettic is less buggy (still buggy but less buggy)
than 0.0.6-SNAPSHOT's. This morning (proper) I experimentally tried integrating
0.0.5's version of integer.c into the develop branch. Many bignum tests
then passed, but others went into non-terminating states. I've reset those
changes.

I've tagged 0.0.5 in the tree so that I can go back to it.

I decided that the responsible thing to do was get the 0.0.6 release out
without these changes, and then have another crack at the bignum problem.

Last night's (or rather, very early this morning's) investigations showed that version 0.0.5's bignum arithmettic is less buggy (still buggy but less buggy) than 0.0.6-SNAPSHOT's. This morning (proper) I experimentally tried integrating 0.0.5's version of `integer.c` into the `develop` branch. Many bignum tests then passed, but others went into non-terminating states. I've reset those changes. I've tagged 0.0.5 in the tree so that I can go back to it. I decided that the responsible thing to do was get the 0.0.6 release out without these changes, and then have another crack at the bignum problem.

simon commented

2026-03-14 21:12:40 +00:00

Author

Owner

OK, I'm now working in the 0.0.6 branch. There are certainly regressions, but I think the problems are more in print than in add.

:: 1152921504606846977

2
:: (inspect 1152921504606846977)

        INTR (1381256777) at page 7, offset 602 count 3
                Integer cell: value 1, count 3
                BIGNUM! More at:
        INTR (1381256777) at page 7, offset 601 count 2
                Integer cell: value 1, count 2

Here, what's printed by inspect looks right, but what's printed by the REPL (and thus by print) is wrong.

:: (+ 1152921504606846975 1152921504606846975)

1,152,921,504,606,846,975
:: (inspect (+ 1152921504606846975 1152921504606846975))

        INTR (1381256777) at page 7, offset 102 count 2
                Integer cell: value 1, count 2
                BIGNUM! More at:
        INTR (1381256777) at page 7, offset 101 count 2
                Integer cell: value 1152921504606846974, count 2

Again, what's printed by inspect looks right, but what's printed by the REPL (and thus by print) is wrong.

OK, I'm now working in the 0.0.6 branch. There are certainly regressions, but I think the problems are more in `print` than in `add`. ```lisp :: 1152921504606846977 2 :: (inspect 1152921504606846977) INTR (1381256777) at page 7, offset 602 count 3 Integer cell: value 1, count 3 BIGNUM! More at: INTR (1381256777) at page 7, offset 601 count 2 Integer cell: value 1, count 2 ``` Here, what's printed by `inspect` looks right, but what's printed by the REPL (and thus by `print`) is wrong. ```lisp :: (+ 1152921504606846975 1152921504606846975) 1,152,921,504,606,846,975 :: (inspect (+ 1152921504606846975 1152921504606846975)) INTR (1381256777) at page 7, offset 102 count 2 Integer cell: value 1, count 2 BIGNUM! More at: INTR (1381256777) at page 7, offset 101 count 2 Integer cell: value 1152921504606846974, count 2 ``` Again, what's printed by `inspect` looks right, but what's printed by the REPL (and thus by `print`) is wrong.

simon commented

2026-03-14 21:15:51 +00:00

Author

Owner

However, in 0.0.6, multiply is definitely wrong:

:: (* 1152921504606846975 2)

1
:: (inspect (* 1152921504606846975 2))

        INTR (1381256777) at page 7, offset 945 count 4294967295
                Integer cell: value 1, count 4294967295
nil

I don't know whether that's a regression or not.

However, in 0.0.6, multiply is definitely wrong: ```lisp :: (* 1152921504606846975 2) 1 :: (inspect (* 1152921504606846975 2)) INTR (1381256777) at page 7, offset 945 count 4294967295 Integer cell: value 1, count 4294967295 nil ``` I don't know whether that's a regression or not.

simon commented

2026-03-14 21:19:43 +00:00

Author

Owner

There is also a bug in add that's definitely a regression:

:: (set! i
  (+
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000))
    
-80

I'm confident that that did work at one time.

There is also a bug in `add` that's definitely a regression: ```lisp :: (set! i (+ 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000)) -80 ``` I'm confident that that did work at one time.

simon commented

2026-03-14 21:25:12 +00:00

Author

Owner

H'mmm... 0.0.5 also gets that wrong, but differently.

:: (+
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000
    10000000000000000000)

7,766,279,631,452,241,920

So not a regression, exactly, but a change.

H'mmm... 0.0.5 also gets that wrong, but differently. ```lisp :: (+ 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000 10000000000000000000) 7,766,279,631,452,241,920 ``` So not a regression, exactly, but a change.

simon commented

2026-03-19 14:25:31 +00:00

Author

Owner

If, as proposed, in 0.1.0 I implement bignums in Lisp, there's a beautiful and easy-to-understand explanation of how they're implemented in ulisp here, which will make life simpler!

If, as proposed, in 0.1.0 I implement bignums in Lisp, there's a beautiful and easy-to-understand explanation of how they're implemented in ulisp [here](http://www.ulisp.com/show?5ARJ), which will make life simpler!

Rows
Columns

The bignum bug(s) #9