FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Assertion failure in bigint

 
Post new topic   Reply to topic     Forum Index -> Deimos
View previous topic :: View next topic  
Author Message
tunah



Joined: 26 Jun 2004
Posts: 4

PostPosted: Sat Jun 26, 2004 11:08 pm    Post subject: Assertion failure in bigint Reply with quote

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 Wink)
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
View user's profile Send private message
tunah



Joined: 26 Jun 2004
Posts: 4

PostPosted: Sat Jun 26, 2004 11:19 pm    Post subject: Reply with quote

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
View user's profile Send private message
tunah



Joined: 26 Jun 2004
Posts: 4

PostPosted: Sun Jun 27, 2004 2:48 am    Post subject: Reply with quote

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
View user's profile Send private message
tunah



Joined: 26 Jun 2004
Posts: 4

PostPosted: Sun Jun 27, 2004 4:25 am    Post subject: Reply with quote

Another bug, in etc.prime
Code:
uint getPrimeLessEqual(uint n)
{
   if (n < 2) assert(false);
   for (n=(n|1)-2; n!=1; n-=2)
   {
      if (isPrime(n)) return n;
   }
   return 2;
}

The fourth line should, I imagine, be
Code:
for(n=(n-1)|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.max-1) isn't assert-worthy IMO.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> Deimos All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
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