Christian Cornelssen on Wed, 5 Sep 2001 01:00:41 +0200 (CEST)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

 Re: addfrac() + Karatsuba = bug

```On Tue, 4 Sep 2001, Michael Somos wrote:

> The following indicates a problem with 'addfrac()' which interacts
> badly with the Karatsuba multiplication in the kernel. It only acts
> up when the numbers get big enough for Karatsuba to kick in. It is
> there in CVS 2.2.1 a few weeks ago. I suggest making the Karatsuba
> threshold a 'default()' settable parameter for user convenience.
>
> parisize = 4000000, primelimit = 500000
> ? add(v1,v2)=[v1*v2+v1*v2,v1*v2]
> ? equ(v1,v2)=v1*v2==v1*v2
> ? frv(x)=[numerator(x),denominator(x)]
> ? tst(x1,x2)=equ(frv(x1+x2),add(frv(x1),frv(x2)))
> ? rn()=random(N)
> ? doit(x,n)=
> {
> N=x;for(i=1,n,
> n0=1+rn;n1=rn;n2=(1+rn)*n0;n3=rn;n4=(1+rn)*n0;print1(tst(n1/n2,n3/n4)))
> }
> ? doit(10^241,10)
> 1011101101

I have tested this on a v2.1.1 built yesterday with most
recently-posted patches, and I get zeros, too.  For one
such case, I have cross-checked add's result with GNU bc,
and found it OK.
I have also verified that n0 divides both components of the result.
It may be worth noting that the numerator of the fractional sum
n1/n2 + n3/n4 was correct, and only the denominator came out wrong.
```