/**************************************************************************** Kalkulon - A programmable calculator for programmers This is an example Kalkulon script. To load from within Kalkulon: Load("examples/scriptname.k") then you can call functions like: funcname() or funcname(arg0, ...) Author: Juergen Holetzeck 2003 - 2008 e-mail: contact@kalkulon.de homepage: www.kalkulon.de ****************************************************************************/ ///////////////////////////////////////////////////////////////////////////// // Thin layer for BIG INTEGER (e.g int64) support, uses bignum.k routines. // While bignums are unlimited and positive, bigints are limited to a certain // bit size and have wrap around and signed/unsigned (2-complement) semantic // JH-2008-02-17 ///////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// // include if(Load("examples/bignum.k"); Error("cannot open file")); ::BIG_NUM_BASE = 0x10000; // 4 hex digits per bignum word, BEWARE: this base is mandatory /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// // configuration // number of bits = INT_SIZE*16, e.g INT_SIZE=4 defines 64 bit arithmetic ::INT_SIZE=4; /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// // Convention for parameter names: // xUBINT -> xUBINT is a Unsigned Big Integer of max INT_SIZE "digits" of base 0x10000 // xSBINT -> xSBINT is a Signed Big Integer in 2-complement of max INT_SIZE "digits" // e.g. for 64 bit Big Integer arithmetic: INT_SIZE = 4 // {N3, N2, N1, N0}, 0<= Ni <= 0xFFFF, e.g. // {0x1234, 0x5678, 0x90ab, 0xcdef} // this is the 64 bit integer "0x1234567890abcdef" // x -> ordinary (float) Kalkulon number, e.g. 123456789 // xU32 -> ordinary (integer) number 0 <= xU32 <= 0xFFFFFFFF /////////////////////////////////////////////////////////////////////////////// // set constants (call this function to change INT_SIZE at runtime) setINTSIZE(int_size) = ( ::INT_SIZE = int_size, ::INT_MAX = {1}+Table(::INT_SIZE,'0'), // max int number = INT_MAX - 1, e.g. 2**64-1 ::INT_MAX2 = {0x8000}+Table(::INT_SIZE-1,'0'), // max negative number = INT_MAX/2, e.g. 2**63 0 ); setINTSIZE(::INT_SIZE); /////////////////////////////////////////////////////////////////////////////// // display functions // print BIGINT in all bases p(xUBINT) = ( printBn(xUBINT), // exact hex printBn(xUBINT, 10, ""), // exact dec if(signBI(xUBINT)==-1; printBn(neg(xUBINT), 10, "-")), // exact signed dec printBn(xUBINT, 2, "0b"), // exact bin xUBINT ); // print last result from interactive session p() = p(out); /////////////////////////////////////////////////////////////////////////////// // conversions: for all values of INT_SIZE // convert float (ordinary) number to big int bint(x) = if(x>=0; chopBI(Bn(x)); neg(Bn(abs(x)))); // bigint from number string in base b, for b > 10 only capital letters are allowed string2BI(s, b) = chopBI(string2Bn(s, b)), // convert UBIGINT to float, BEWARE: for big numbers some precision is lost u2f(xUBINT) = Bn2float(xUBINT); // convert SBIGINT to float, BEWARE: for big numbers some precision is lost i2f(xSBINT) = if(signBI(xSBINT)==-1; -u2f(neg(xSBINT)); u2f(xSBINT)); /////////////////////////////////////////////////////////////////////////////// // conversions: 64 bit only (INT_SIZE == 4) // convert float (ordinary) number to U64/I64 u64(x) = bint(x); // build U64 from two U32 u64(hiU32, loU32) = normBn({(hiU32&0xffff0000)>>16, hiU32&0xffff, (loU32&0xffff0000)>>16, loU32&0xffff}); // build U64 from four U16 u64(hi1U16, lo1U16, hi0U16, lo0U16) = normBn({(u16)hi1U16, (u16)lo1U16, (u16)hi0U16, (u16)lo0U16}); // hi and lo dword (U32) from U64 hidword64(xUBINT) = (xUBINT=expandBI(xUBINT), (xUBINT[0]<<16)|xUBINT[1]); lodword64(xUBINT) = (xUBINT=expandBI(xUBINT), (xUBINT[2]<<16)|xUBINT[3]); /////////////////////////////////////////////////////////////////////////////// // arithmetic and logic // add (signed/unsigned) add(xUBINT, yUBINT) = chopBI(addBn(xUBINT, yUBINT)); // substract (signed/unsigned) sub(xUBINT, yUBINT) = subBn(expandBI(xUBINT), yUBINT); // muliply (signed/unsigned) mul(xUBINT, yUBINT) = chopBI(mulBn(xUBINT, yUBINT)); // divide (unsigned only!) div(xUBINT, yUBINT) = divBn(xUBINT, yUBINT); // neg (x -> -x) neg(xSBINT) = subBn(::INT_MAX, xSBINT); // sign signBI(xSBINT) = if((Size(xSBINT)==::INT_SIZE && (xSBINT[0] & 0x8000));-1;1); // abs absBI(xSBINT) = if(signBI(xSBINT)==-1; if(xSBINT==::INT_MAX2;Error("overflow");neg(xSBINT)); xSBINT); // not not(xUBINT) = ForEach(expandBI(xUBINT),'(u16)~#'); // and and(xUBINT, yUBINT) = normBn(ForEach(expandBI(xUBINT), expandBI(yUBINT), '#1')); // or or(xUBINT, yUBINT) = normBn(ForEach(expandBI(xUBINT), expandBI(yUBINT), '#1|#2')); // xor xor(xUBINT, yUBINT) = normBn(ForEach(expandBI(xUBINT), expandBI(yUBINT), '#1^#2')); // shift left shl(xUBINT, n)= ( xUBINT=Sub(expandBI(xUBINT),floor(n/16)), while(Size(xUBINT)<::INT_SIZE;xUBINT+={0}), for(r=fmod(n,16), carry=0, i=::INT_SIZE-1; i>=0; --i; xUBINT[i]=(t=xUBINT[i]<>16), normBn(xUBINT) ); // shift right shr(xUBINT, n)= ( xUBINT=expandBI(Sub(expandBI(xUBINT),0,::INT_SIZE-floor(n/16))), for(r=fmod(n,16), carry=0, i=0; i<::INT_SIZE; ++i; t=(xUBINT[i]<<=(16-r))&0xffff, xUBINT[i]=(xUBINT[i]>>16)|carry, carry=t), normBn(xUBINT) ); /////////////////////////////////////////////////////////////////////////////// // compare // unsigned compare: -1 for x y compareBI_u(xUBINT, yUBINT) = compareBn(xUBINT, yUBINT); // signed compare: -1 for x y compareBI_s(xSBINT, ySBINT) = ( xs=signBI(xSBINT), if(xs==signBI(ySBINT); compareBn(xSBINT, ySBINT); if(xs==-1;-1;1)) ); /////////////////////////////////////////////////////////////////////////////// // helper functions // limit bignum to BIGINT chopBI(xBn) = normBn(chopBn(xBn , ::INT_SIZE)); // expand bignum to BIGINT expandBI(xBn) = expandBn(xBn, ::INT_SIZE);