The bignum multiply bug

[simon-brooke]

I'm writing a problem now (commit #bf72ae379d180b4fb773bb48920e4628e55be895) because I think I'm close to getting this right.

Two areas of problem exist, both happen at exactly the bignum barrier. The problem area is in lines 239-278 of integer.c:

1. I'm decrementing a reference I should not decrement. In this commit GC is disabled, because I cannot track down where the bad dec_ref is. Obviously, in the medium term this must be fixed, but for the time being I'm just trying to get the algorithm right.
2. As the barrier is crossed, we should get a new bignum [0]->[1]; in fact we get one [576460752303423489]->[0]->[1]; in other words we get a spurious least significant cell, and I think it's because of mishandling the carry.

The value that's delivered at (expt 2 60) is:

:: (inspect (expt 2 60))

	INTR (1381256777) at page 23, offset 641 count 2
		Integer cell: value 576460752303423489, count 2
		BIGNUM! More at:
	INTR (1381256777) at page 23, offset 640 count 1
		Integer cell: value 0, count 1
		BIGNUM! More at:
	INTR (1381256777) at page 23, offset 639 count 1
		Integer cell: value 1, count 1
1,152,921,504,606,846,977,729,382,256,910,270,464

In fact the result should be:

* (expt 2 60)

1,152,921,504,606,846,976

So: where does it go wrong? Looking at the log:

multiply_2( arg1 = 2; arg2 = 576,460,752,303,423,488)
multiply_integers: a = 2; b = 576,460,752,303,423,488
cell_value: raw value is 2, is_first_cell = true; INTR; returning 2
cell_value: raw value is 576460752303423488, is_first_cell = true; INTR; returning 576460752303423488
multiply_integers: d = 2; dv = 2; bv = 576460752303423488; carry = 0; rv = 1152921504606846976; acc = nil; partial = 0
int128_to_integer: 64 bit overflow; setting carry to 1
cell_value: raw value is 0, is_first_cell = false; NIL ; returning 1
cell_value: raw value is 576460752303423488, is_first_cell = true; INTR; returning 576460752303423488
multiply_integers: d = nil; dv = 1; bv = 576460752303423488; carry = 1; rv = 576460752303423489; acc = nil; partial = 1,152,921,504,606,846,975
add_integers: a = 1,152,921,504,606,846,975; b = 576,460,752,303,423,489
add_integers: 
	INTR (1381256777) at page 23, offset 717 count 0
		Integer cell: value 0, count 0
		BIGNUM! More at:
	INTR (1381256777) at page 23, offset 720 count 1
		Integer cell: value 0, count 1
 plus 
	INTR (1381256777) at page 23, offset 716 count 1
		Integer cell: value 576460752303423489, count 1

cell_value: raw value is 0, is_first_cell = true; INTR; returning 0
cell_value: raw value is 576460752303423489, is_first_cell = true; INTR; returning 576460752303423489
add_integers: av = 0; bv = 576460752303423489; carry = 0; rv = 576460752303423489
cell_value: raw value is 0, is_first_cell = false; INTR; returning 1152921504606846976
cell_value: raw value is 0, is_first_cell = false; NIL ; returning 0
add_integers: av = 1152921504606846976; bv = 0; carry = 0; rv = 1152921504606846976
int128_to_integer: 64 bit overflow; setting carry to 1
cell_value: raw value is 0, is_first_cell = false; NIL ; returning 0
cell_value: raw value is 0, is_first_cell = false; NIL ; returning 0
add_integers: av = 0; bv = 0; carry = 1; rv = 1
add_integers returning: 1,152,921,504,606,846,977,729,382,256,910,270,464
multiply_integers returning: 1,152,921,504,606,846,977,729,382,256,910,270,464
multiply_2 returning: 1,152,921,504,606,846,977,729,382,256,910,270,464
lisp_multiply returning: 1,152,921,504,606,846,977,729,382,256,910,270,464

At the line

add_integers: a = 1,152,921,504,606,846,975; b = 576,460,752,303,423,489

what we should be adding is 1. So why are we adding MAX_INTEGER + 2? Because we didn't divide the carry down by MAX_INTEGER as we crossed to the next cell? Or should we be decrementing it by MAX_INTEGER + 1? My hunch is it's divide...

[simon-brooke]

Wrong.

The preceding multiply_integers line is:

multiply_integers: d = nil; dv = 1; bv = 576460752303423488; carry = 1; rv = 576460752303423489; acc = nil; partial = 1,152,921,504,606,846,975

d - the 'digit' - is nil. But 'dv' - the value assigned for the digit - is 1. And I'm doing that because 1 is the multiplicative identity, but here it is clearly wrong.