// Rascal, the Advanced Scientific CALculator
// Copyright (C) 2001, Sebastian Ritterbusch (Rascal@Ritterbusch.de)
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more detauls.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//
// Long Integer Library
// (C) 1999 Jochen Suckfüll
// (C) 2001 Sebastian Ritterbusch
#include "langzahl.hpp"
#include <stdio.h>
init_rand randomstate;
#ifdef RESPECT_RASCAL_USER_STOP_VARIABLE
#define LZ_USER_STOP_CONDITION && !rascal_user_stop
#else
#define LZ_USER_STOP_CONDITION
#endif
langzahl::langzahl(LONG32 i) throw()
{
if(i==0)
{
dat=0;
longs=0;
sign=0;
return;
}
if(i<0)
{
sign=-1;
i=-i;
} else
sign=0;
if(i>=100000000)
longs=2;
else
longs=1;
dat=new LONG32[longs];
dat[0]=i%100000000;
if(longs==2)
dat[1]=i/100000000;
}
langzahl::langzahl(const lsize &s) throw():longs(s.size()),sign(0)
{
dat=new LONG32[longs];
for(int i=0;i<longs;i++)
dat[i]=0;
}
langzahl::langzahl(const string &s) throw()
{
LONG32 fak,st;
if(s[0]=='-')
sign=-1;
else
sign=0;
longs=(s.length()-1)/8+1;
dat=new LONG32[longs];
st=s.length()-(longs-1)*8;
dat[longs-1]=0;
for(int i=st-1,fak=1;(i>=-sign) LZ_USER_STOP_CONDITION;i--,fak*=10)
dat[longs-1]+=(s[i]-'0')*fak;
st-=sign;
for(int i=0;(i<longs-1) LZ_USER_STOP_CONDITION;i++)
{
fak=1;
dat[i]=0;
for(int j=1;j<=8;j++,fak*=10)
dat[i]+=(s[st+(longs-1-i)*8-j]-'0')*fak;
}
kuerze();
}
langzahl::langzahl(const langzahl &l) throw():longs(l.longs),sign(l.sign)
{
dat=new LONG32[longs];
for(int i=0;i<longs;i++)
dat[i]=l.dat[i];
}
inline void langzahl::kuerze() throw()
{
for(;longs&&dat[longs-1]==0;longs--);
if(longs==0)
sign=0;
}
istream &operator >>(istream &is,langzahl &l) throw()
{
string s;
is>>s;
l=langzahl(s);
return is;
}
string &operator >>(string &is,langzahl &l) throw()
{
l=langzahl(is);
return (is="");
}
ostream &operator <<(ostream &os,const langzahl &l) throw()
{
if(l.sign) os<<'-';
if(l.longs) os<<l.dat[l.longs-1];
else os<<"0";
for(int i=l.longs-2;(i>=0) LZ_USER_STOP_CONDITION;i--)
os<<std::setw(8)<<std::setfill('0')<<l.dat[i];
return os;
}
string langzahl_long2string(LONG32 a)
{
char buffer[9];
sprintf(buffer,"%i",a);
return string(buffer);
}
string &operator <<(string &os,const langzahl &l) throw()
{
if(l.sign) os+='-';
if(l.longs) os+=langzahl_long2string(l.dat[l.longs-1]);
else os+='0';
for(int i=l.longs-2;(i>=0) LZ_USER_STOP_CONDITION;i--)
{
string n(langzahl_long2string(l.dat[i]));
for(int k=0;k<8-n.length();k++)
os+='0';
os+=n;
}
return os;
}
langzahl &langzahl::operator =(const langzahl &l2) throw()
{
longs=l2.longs;
sign=l2.sign;
LONG32 * newdat=new LONG32[longs];
for(int i=0;i<longs;i++)
newdat[i]=l2.dat[i];
delete [] dat;
dat=newdat;
return *this;
}
langzahl &langzahl::operator =(LONG32 i) throw()
{
delete [] dat;
if(i==0)
{
dat=0;
longs=0;
sign=0;
return *this;
}
if(i<0)
{
sign=-1;
i=-i;
}
if(i>=100000000)
longs=2;
else
longs=1;
dat=new LONG32[longs];
dat[0]=i%100000000;
if(longs==2)
dat[1]=i/100000000;
return *this;
}
langzahl &langzahl::operator =(const char *c) throw()
{
*this=string(c);
return *this;
}
bool operator ==(const langzahl &l1,const langzahl &l2) throw()
{
if(l1.sign!=l2.sign) return false;
if(l1.longs!=l2.longs) return false;
for(int i=0;i<l1.longs;i++)
if(l1.dat[i]!=l2.dat[i]) return false;
return true;
}
bool operator !=(const langzahl &l1,const langzahl &l2) throw()
{
if(l1.sign!=l2.sign) return true;
if(l1.longs!=l2.longs) return true;
for(int i=0;i<l1.longs;i++)
if(l1.dat[i]!=l2.dat[i]) return true;
return false;
}
bool operator <=(const langzahl &l1,const langzahl &l2) throw()
{
if(l1.sign<l2.sign) return true;
if(l1.sign>l2.sign) return false;
if(l1.longs>l2.longs) return l1.sign==0?false:true;
if(l1.longs<l2.longs) return l1.sign==0?true:false;
for(int i=l1.longs-1;i>=0;i--)
{
if(l1.dat[i]>l2.dat[i]) return l1.sign==0?false:true;
if(l1.dat[i]<l2.dat[i]) return l1.sign==0?true:false;
}
return true;
}
bool operator >=(const langzahl &l1,const langzahl &l2) throw()
{
if(l1.sign<l2.sign) return false;
if(l1.sign>l2.sign) return true;
if(l1.longs<l2.longs) return l1.sign==0?false:true;
if(l1.longs>l2.longs) return l1.sign==0?true:false;
for(int i=l1.longs-1;i>=0;i--)
{
if(l1.dat[i]<l2.dat[i]) return l1.sign==0?false:true;
if(l1.dat[i]>l2.dat[i]) return l1.sign==0?true:false;
}
return true;
}
bool operator <(const langzahl &l1,const langzahl &l2) throw()
{
if(l1.sign<l2.sign) return true;
if(l1.sign>l2.sign) return false;
if(l1.longs>l2.longs) return l1.sign==0?false:true;
if(l1.longs<l2.longs) return l1.sign==0?true:false;
for(int i=l1.longs-1;i>=0;i--)
{
if(l1.dat[i]>l2.dat[i]) return l1.sign==0?false:true;
if(l1.dat[i]<l2.dat[i]) return l1.sign==0?true:false;
}
return false;
}
bool operator >(const langzahl &l1,const langzahl &l2) throw()
{
if(l1.sign<l2.sign) return false;
if(l1.sign>l2.sign) return true;
if(l1.longs<l2.longs) return l1.sign==0?false:true;
if(l1.longs>l2.longs) return l1.sign==0?true:false;
for(int i=l1.longs-1;i>=0;i--)
{
if(l1.dat[i]<l2.dat[i]) return l1.sign==0?false:true;
if(l1.dat[i]>l2.dat[i]) return l1.sign==0?true:false;
}
return false;
}
bool eqzero(const langzahl &l) throw()
{
if(l.longs>1) return false;
if(l.longs==0||l.dat[0]==0) return true;
return false;
}
bool grzero(const langzahl &l) throw()
{
if(l.sign||!l.longs) return false;
if(l.longs>1||l.dat[0]>0) return true;
return false;
}
bool ltzero(const langzahl &l) throw()
{
if(!l.sign||!l.longs) return false;
if(l.longs>1||l.dat[0]>0) return true;
return false;
}
langzahl operator -(const langzahl &l) throw()
{
langzahl e(l);
if(e.sign)
e.sign=0;
else
e.sign=-1;
e.kuerze();
return e;
}
langzahl operator %(langzahl l,langzahl m) throw()
{
int len;
langzahl fak;
int lsign=l.sign;
l.sign=0;
m.sign=0;
if(m.longs==0)
return l;
len=l.longs-m.longs;
fak=1;
while((m*fak<=l) LZ_USER_STOP_CONDITION)
fak*=10;
fak/=10;
langzahl e(l);
while((fak) LZ_USER_STOP_CONDITION)
{
while((m*fak<=e) LZ_USER_STOP_CONDITION)
e-=m*fak;
fak/=10;
}
if(e.sign) e=_llminus(m,e);
if(lsign)
{
if(e.sign)
e.sign=0;
else
e.sign=-1;
}
e.kuerze();
return e;
}
langzahl operator /(langzahl l,langzahl m) throw()
{
if(m.longs==0) // Division by zero
return l;
int len;
langzahl fak;
int sign=m.sign;
int lsign=l.sign;
m.sign=0;
l.sign=0;
len=l.longs-m.longs;
fak=1;
while((m*fak<=l) LZ_USER_STOP_CONDITION)
fak*=10;
fak/=10;
langzahl e(l),d(0);
while((fak) LZ_USER_STOP_CONDITION)
{
while((m*fak<=e) LZ_USER_STOP_CONDITION)
{
e-=m*fak;
d+=fak;
}
fak/=10;
}
if(e.sign) d+=1;
if((sign==0 && lsign==-1) || (sign==-1 && lsign==0))
{
if(d.sign)
d.sign=0;
else
d.sign=-1;
}
d.kuerze();
return d;
}
inline langzahl _llplus(const langzahl &l1,const langzahl &l2) throw()
{
int i;
langzahl e(lsize(l1.longs+1));
for(i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
{
e.dat[i]+=l1.dat[i]+l2.dat[i];
if(e.dat[i]>99999999)
{
e.dat[i]-=100000000;
e.dat[i+1]=1;
}
}
for(;(i<l1.longs) LZ_USER_STOP_CONDITION;i++)
{
e.dat[i]+=l1.dat[i];
if(e.dat[i]>99999999)
{
e.dat[i]-=100000000;
e.dat[i+1]=1;
}
}
e.kuerze();
return e;
}
inline langzahl _llminus(const langzahl &l1,const langzahl &l2) throw()
{
int i;
langzahl e(lsize(l1.longs+1));
for(i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
{
e.dat[i]+=l1.dat[i]-l2.dat[i];
if(e.dat[i]<0)
{
e.dat[i]+=100000000;
e.dat[i+1]=-1;
}
}
for(;(i<l1.longs) LZ_USER_STOP_CONDITION;i++)
{
e.dat[i]+=l1.dat[i];
if(e.dat[i]<0)
{
e.dat[i]+=100000000;
e.dat[i+1]=-1;
}
}
e.kuerze();
return e;
}
langzahl operator +(const langzahl &l1,const langzahl &l2) throw()
{
if(l1.sign)
{
if(l2.sign)
{
if(l1<l2)
return -(_llplus(-l1,-l2));
else
return -(_llplus(-l2,-l1));
}
else
{
if((-l1)>=l2)
return -(_llminus(-l1,l2));
else
return _llminus(l2,-l1);
}
}
else
{
if(l2.sign)
{
if(l1>=(-l2))
return _llminus(l1,-l2);
else
return -(_llminus(-l2,l1));
}
else
{
if(l1>=l2)
return _llplus(l1,l2);
else
return _llplus(l2,l1);
}
}
}
langzahl operator -(const langzahl &l1,const langzahl &l2) throw()
{
if(l1.sign)
{
if(l2.sign)
{
if(l2>=l1)
return -(_llminus(-l1,-l2));
else
return (_llminus(-l2,-l1));
}
else
{
if((-l1)>=l2)
return -(_llplus(-l1,l2));
else
return -(_llplus(l2,-l1));
}
}
else
{
if(l2.sign)
{
if(l1>=(-l2))
return _llplus(l1,-l2);
else
return _llplus(-l2,l1);
}
else
{
if(l1>=l2)
return _llminus(l1,l2);
else
return -_llminus(l2,l1);
}
}
}
langzahl operator *(const langzahl &l1,const langzahl &l2) throw()
{
langzahl e(lsize(l1.longs+l2.longs));
int d,z,zw1;
for(int i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
{
z=l2.dat[i];
for(int j=0,fak=10000000,mod=10;(j<8) LZ_USER_STOP_CONDITION;j++,fak/=10,mod*=10)
{
d=z/fak;
z-=d*fak;
for(int k=0;(k<l1.longs) LZ_USER_STOP_CONDITION;k++)
{
zw1=l1.dat[k]*d;
e.dat[i+k]+=(zw1%mod)*fak;
e.dat[i+k+1]+=zw1/mod+(e.dat[i+k]/100000000);
e.dat[i+k]%=100000000;
}
}
}
if(l1.sign+l2.sign==-1) e.sign=-1;
else e.sign=0;
e.kuerze();
return e;
}
inline void div2(langzahl &l) throw()
{
int i;
for(i=0;(i<l.longs-1) LZ_USER_STOP_CONDITION;i++)
{
l.dat[i]=(l.dat[i]>>1);
if(l.dat[i+1]&1) l.dat[i]+=50000000;
}
l.dat[i]=l.dat[i]>>1;
l.kuerze();
}
// Achtung: Ergebnis ist nicht gekuerzt!
inline void mul2(langzahl &l) throw()
{
if(l.dat[l.longs-1]>=50000000)
{
LONG32 *ndat=new LONG32[l.longs+1];
ndat[l.longs]=0;
for(int i=l.longs-1;(i>=0) LZ_USER_STOP_CONDITION;i--)
{
ndat[i]=l.dat[i]<<1;
if(ndat[i]>=100000000)
{
ndat[i]-=100000000;
ndat[i+1]++;
}
}
l.longs++;
delete [] l.dat;
l.dat=ndat;
}
else
{
for(int i=l.longs-1;(i>=0) LZ_USER_STOP_CONDITION;i--)
{
l.dat[i]=l.dat[i]<<1;
if(l.dat[i]>=100000000)
{
l.dat[i]-=100000000;
l.dat[i+1]++;
}
}
}
}
langzahl &langzahl::operator +=(const langzahl &l2) throw()
{
*this=*this+l2;
// int i;
// longs=MAX(longs,l2.longs)+1;
// int *ndat=new int[longs];
// for(i=0;i<longs;i++)
// ndat[i]=dat[i];
// for(;i<longs;i++)
// ndat[i]=0;
// for(i=0;i<l2.longs;i++)
// {
// ndat[i]+=l2.dat[i];
// if(ndat[i]>99999999)
// {
// ndat[i]-=100000000;
// ndat[i+1]+=1;
// }
// }
// delete [] dat;
// dat=ndat;
// kuerze();
return *this;
}
langzahl &langzahl::operator -=(const langzahl &l2) throw()
{
*this=*this-l2;
// int i;
// longs=MAX(longs,l2.longs);
// int *ndat=new int[longs];
// for(i=0;i<longs;i++)
// ndat[i]=dat[i];
// for(;i<longs;i++)
// ndat[i]=0;
// for(i=0;i<l2.longs;i++)
// {
// ndat[i]-=l2.dat[i];
// if(ndat[i]<0)
// {
// ndat[i]+=100000000;
// ndat[i+1]-=1;
// }
// }
// delete [] dat;
// dat=ndat;
// kuerze();
return *this;
}
langzahl &langzahl::operator *=(const langzahl &l2) throw()
{
LONG32 *ndat=new LONG32[longs+l2.longs];
for(int i=0;(i<longs+l2.longs) LZ_USER_STOP_CONDITION;i++)
ndat[i]=0;
LONG32 d,z,zw1;
for(int i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
{
z=l2.dat[i];
for(int j=0,fak=10000000,mod=10;(j<8) LZ_USER_STOP_CONDITION;j++,fak/=10,mod*=10)
{
d=z/fak;
z-=d*fak;
for(int k=0;(k<longs) LZ_USER_STOP_CONDITION;k++)
{
zw1=dat[k]*d;
ndat[i+k]+=(zw1%mod)*fak;
ndat[i+k+1]+=zw1/mod+(ndat[i+k]/100000000);
ndat[i+k]%=100000000;
}
}
}
if(sign+l2.sign==-1) sign=-1;
longs+=l2.longs;
delete [] dat;
dat=ndat;
kuerze();
return *this;
}
langzahl &langzahl::operator %=(const langzahl &m) throw()
{
int len;
langzahl fak;
if(m.longs==0)
return *this;
len=longs-m.longs;
fak=1;
while((m*fak<*this) LZ_USER_STOP_CONDITION)
fak*=10;
fak/=10;
while((fak) LZ_USER_STOP_CONDITION)
{
while((m*fak<=*this) LZ_USER_STOP_CONDITION)
*this-=m*fak;
fak/=10;
}
if(sign) *this=_llminus(m,*this);
kuerze();
return *this;
}
langzahl addm(const langzahl &l1,const langzahl &l2,const langzahl &m) throw()
{
int i;
langzahl e(lsize(l1.longs+1));
for(i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
{
e.dat[i]+=l1.dat[i]+l2.dat[i];
if(e.dat[i]>99999999)
{
e.dat[i]-=100000000;
e.dat[i+1]=1;
}
}
for(;(i<l1.longs) LZ_USER_STOP_CONDITION;i++)
{
e.dat[i]+=l1.dat[i];
if(e.dat[i]>99999999)
{
e.dat[i]-=100000000;
e.dat[i+1]=1;
}
}
e.kuerze();
return e%m;
}
//hier noch optimieren! Analog normalem Minus, mit Vorzeichenwechsel!
langzahl subm(const langzahl &l1,const langzahl &l2,const langzahl &m) throw()
{
int i;
langzahl e(lsize(l1.longs+1)),corr(l1);
while((l2>corr) LZ_USER_STOP_CONDITION)
corr=corr+m;
for(i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
{
e.dat[i]+=corr.dat[i]-l2.dat[i];
if(e.dat[i]<0)
{
e.dat[i]+=100000000;
e.dat[i+1]=-1;
}
}
for(;(i<corr.longs) LZ_USER_STOP_CONDITION;i++)
{
e.dat[i]+=corr.dat[i];
if(e.dat[i]<0)
{
e.dat[i]+=100000000;
e.dat[i+1]=-1;
}
}
e.kuerze();
return e%m;
}
langzahl multm(const langzahl &l1,const langzahl &l2,const langzahl &m) throw()
{
langzahl e(lsize(l1.longs+l2.longs));
LONG32 d,z,zw1;
for(int i=0;(i<l2.longs) LZ_USER_STOP_CONDITION;i++)
{
for(int k=0;(k<l1.longs) LZ_USER_STOP_CONDITION;k++)
{
z=l2.dat[i];
for(int j=0,fak=10000000,mod=10;(j<8) LZ_USER_STOP_CONDITION;j++,fak/=10,mod*=10)
{
d=z/fak;
z-=d*fak;
zw1=l1.dat[k]*d;
e.dat[i+k]+=(zw1%mod)*fak;
e.dat[i+k+1]+=zw1/mod+(e.dat[i+k]/100000000);
e.dat[i+k]%=100000000;
}
}
}
e.kuerze();
return e%m;
}
langzahl potm(const langzahl &l,const int n,const langzahl &m) throw()
{
langzahl e(1),a(l);
int b(n);
while((b>1) LZ_USER_STOP_CONDITION)
{
if(b&1)
{
b--;
e*=a; // testen, ob sich hier ein % lohnt!! <===============
}
b=b>>1;
a*=a;
a%=m;
}
e*=a;
return e%m;
}
langzahl pow(const langzahl &l,const langzahl &n) throw()
{
langzahl e(1),a(l),b(n);
while((b>1) LZ_USER_STOP_CONDITION)
{
if(b.dat[0]&1)
{
b.dat[0]--;
e*=a;
}
div2(b);
a*=a;
}
e*=a;
if((n.dat[0]&1)==0 && l.sign)
e.sign=0;
return e;
}
langzahl potm(const langzahl &l,const langzahl &n,const langzahl &m) throw()
{
langzahl e(1),a(l),b(n);
while((b>1) LZ_USER_STOP_CONDITION)
{
if(b.dat[0]&1)
{
b.dat[0]--;
e*=a; // testen, ob sich hier ein % lohnt!! <===============
}
div2(b);
a*=a;
a%=m;
}
e*=a;
return e%m;
}
langzahl pow(const langzahl &l1,const LONG32 n) throw()
{
langzahl e(1),a(l1);
int b=n;
while((b>1) LZ_USER_STOP_CONDITION)
{
if(b&1)
{
b--;
e*=a;
}
b>>1;
a*=a;
}
e*=a;
return e;
}
langzahl operator *=(langzahl &l1,const LONG32 n) throw()
{
LONG32 *ndat=new LONG32[l1.longs+1];
for(int i=0;(i<l1.longs+1) LZ_USER_STOP_CONDITION;i++)
ndat[i]=0;
LONG32 d,z,zw1;
for(int k=0;(k<l1.longs) LZ_USER_STOP_CONDITION;k++)
{
z=n;
for(int j=0,fak=10000000,mod=10;(j<8) LZ_USER_STOP_CONDITION;j++,fak/=10,mod*=10)
{
d=z/fak;
z-=d*fak;
zw1=l1.dat[k]*d;
ndat[k]+=(zw1%mod)*fak;
ndat[k+1]+=zw1/mod;
}
}
l1.longs++;
delete [] l1.dat;
l1.dat=ndat;
l1.kuerze();
return l1;
}
langzahl operator /=(langzahl &l,const LONG32 n) throw()
{
const LONG32 mod=100000000%n;
const LONG32 div=100000000/n;
LONG32 rest=0;
LONG32 *ndat=new LONG32[l.longs];
ndat[l.longs-1]=0;
for(int i=l.longs-1;(i>0) LZ_USER_STOP_CONDITION;i--)
{
ndat[i]+=(l.dat[i]+rest*mod)/n;
rest=l.dat[i]%n;
ndat[i-1]=div*rest;
}
ndat[0]+=l.dat[0]/n;
delete [] l.dat;
l.dat=ndat;
l.kuerze();
return l;
}
langzahl ggT(const langzahl &l1,const langzahl &l2) throw()
{
langzahl a,b,c;
// if(l1+l2==0)
// cerr<<"Kann keinen ggT bilden von "<<l1<<" und "<<l2<<"!"<<endl;
a=l1;
b=l2;
c=b;
while((grzero(a) LZ_USER_STOP_CONDITION))
{
c=a;
a=b%a;
b=c;
}
return c;
}
// hier wird nur pseudoprim bzgl a getestet, man sollte mehrere a probieren!
bool pprim(const langzahl &n,const langzahl &a) throw()
{
int i=0,k;
langzahl m(n),b;
m-=1;
k=0;
while((!(m.dat[0]&1) LZ_USER_STOP_CONDITION))
{
div2(m);
k++;
}
if(ggT(n,a)!=1) return false; // ist der ggT wirklich noetig?
b=potm(a,m,n);
if(b==1||b==n-1) return true;
for(i=1;((b!=1)&&(i<k)&&(b!=n-1)) LZ_USER_STOP_CONDITION;i++)
{
b*=b;
b%=n;
}
if(b==1) return false;
if(b==n-1) return true;
return false;
}
langzahl lrandom(int n) throw()
{
lsize size(n);
langzahl e(size);
for(int i=0;(i<n) LZ_USER_STOP_CONDITION;i++)
e.dat[i]=rand()%100000000;
e.kuerze();
return e;
}
/* die hier muss noch geprueft werden
langzahl findprim(int n) throw()
{
lsize size(n);
langzahl e(size),d(1);
const int a[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59 };
do
{
for(int i=0;(i<n) LZ_USER_STOP_CONDITION;i++)
e.dat[i]=rand()%100000000;
e.dat[0]|=1;
for(int i=0;i<17;i++)
d*=a[i];
} while(((ggT(d,e)!=1)||(!pprim(e,random()))||(!pprim(e,random()))||(!pprim(e,random()))) LZ_USER_STOP_CONDITION);
return e;
}
*/
langzahl fak(LONG32 k) throw()
{
langzahl e(1);
for(;(k>1) LZ_USER_STOP_CONDITION;k--)
e=e*k;
return e;
}
langzahl fak(LONG32 k,const langzahl &n) throw()
{
langzahl e(1);
for(;(k>1) LZ_USER_STOP_CONDITION;k--)
e=multm(e,k,n);
return e;
}
// hier sollten noch Verfeinerungen angebracht werden
langzahl pollard(const langzahl &n) throw()
{
langzahl e,m;
LONG32 k(1);
m=potm(2,fak(k),n);
e=ggT(m-1,n);
while(((e==1)&&(e!=n)) LZ_USER_STOP_CONDITION)
{
k+=2;
m=potm(m,k*(k-1),n);
e=ggT(m-1,n);
}
return e;
}
/*
void lsh3(langzahl &l) throw()
{
LONG32 d;
for(int i=l.longs-1;i>0;i--)
{
l.dat[i]=l.dat[i]<<3;
l.dat[i]=;
*/
int langzahl::operator !() const throw()
{
for(int i=0;i<longs;i++)
if(dat[i]) return(false);
return true;
}
syntax highlighted by Code2HTML, v. 0.9.1