View previous topic :: View next topic 
Author 
Message 
tunah
Joined: 26 Jun 2004 Posts: 4

Posted: Sat Jun 26, 2004 11:08 pm Post subject: Assertion failure in bigint 


Thanks a lot for bigint, it's excellent! (A lot more fun than in java, someone needs to tell them that OO can stand for operator overloading )
I hit a problem though:
Code:  import etc.bigint.bigint;
int main() {
Int a=new Int("400000000000000000000000000000000000000");
Int b=new Int("400000000000000000000000000000000000001");
Int c=a*b;
printf("?.*s\n",c.toString);
return 0;
} 
The above code causes an assertion error in the multiplication.
It will be triggered with any larger value for b, but not for any smaller value, afaics. Reducing a below a certain point will also stop the assertion failing, the critical point is somewhere between 34028000.... and 34029000...
The failure is multiply.d line 143:
Code:  void bigintMulKaratsuba(uint* d, uint* x, uint X, uint* y, uint Y)
out
{
uint[] check;
check.length = X+Y;
bigintMulClassic(check, x, X, y, Y);
assert(bigintLLEquals(d, check, X+Y));
check[] = 0;
} 
I don't know the algorithm, so I can't work out why it's failing.
It's the Karatsuba, not the Classic that's failing though, compiling in release mode gives a calculation result of:
24230268069311136653709320907920185040084931295110969712435179334010438202599155
9577600 

Back to top 


tunah
Joined: 26 Jun 2004 Posts: 4

Posted: Sat Jun 26, 2004 11:19 pm Post subject: 


While I'm here, I'm wondering if you might reconsider the lack of destructive operations? While they wouldn't be very useful to me in this case AFAICS (exponentiating numbers of the form a+b sqrt(p)), mutable operations would give a big speedup in a lot of situations, I'd imagine.
Of course there'd have to be a big warning that modifying values without duping means you lose value semantics, and that modifying ONE or ZERO is going to result in undefined, or at least very odd, behaviour... 

Back to top 


tunah
Joined: 26 Jun 2004 Posts: 4

Posted: Sun Jun 27, 2004 2:48 am Post subject: 


There's also a problem with the ge2 function which causes the fast gcd() to sometimes fail.
Code:  // get the number of trailing zero bits in this (ge2 means Greatest Power of 2)
uint ge2(Int x)
{
for (uint i=0; i<x.d.length; ++i)
{
int n = bsf(x.d[i]);
if (n >= 0) return n;
}
throw new IntException("ge2(x) not defined for x == 0");
} 
This assumes that bsf returns negative when given 0, in fact behaviour is undefined, and dmd 0.93 on win32 returns 1 for me.
Also, it doesn't take account of which data element the first set bit was in.
This fixes both:
Code:  // get the number of trailing zero bits in this (ge2 means Greatest Power of 2)
uint ge2(Int x)
{
for (uint i=0; i<x.d.length; ++i)
{
if(x.d[i]==0)
continue;
int n = bsf(x.d[i]);
if (n >= 0) return n + i*x.d[0].sizeof*8;
}
throw new IntException("ge2(x) not defined for x == 0");
} 
The ge2(uint) has the first problem, the fix is:
Code:  uint ge2(uint x)
{
if(x==0)
throw new IntException("ge2(x) not defined for x == 0");
return bsf(x);
}



Back to top 


tunah
Joined: 26 Jun 2004 Posts: 4

Posted: Sun Jun 27, 2004 4:25 am Post subject: 


Another bug, in etc.prime
Code:  uint getPrimeLessEqual(uint n)
{
if (n < 2) assert(false);
for (n=(n1)2; n!=1; n=2)
{
if (isPrime(n)) return n;
}
return 2;
} 
The fourth line should, I imagine, be
Code:  for(n=(n1)1; n!=1; n=2) 
As it is, getPrimeLessEqual(5) returns 3, not 5.
Also, it might be better to have getPrimeGreaterEqual return 0 or throw an exception instead of asserting false if there are no bigger primes that fit inside uints, getPrimeGreaterEqual(uint.max1) isn't assertworthy IMO. 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
