Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{1
- --
- -- File Name: bignum.lua
- -- Package Name: BigNum
- --
- -- Project: Big Numbers library for Lua
- -- Mantainers: fmp - Frederico Macedo Pessoa
- -- msm - Marco Serpa Molinaro
- --
- -- History:
- -- Version Autor Date Notes
- -- 1.1 fmp/msm 12/11/2004 Some bug fixes (thanks Isaac Gouy)
- -- alfa fmp/msm 03/22/2003 Start of Development
- -- beta fmp/msm 07/11/2003 Release
- --
- -- Description:
- -- Big numbers manipulation library for Lua.
- -- A Big Number is a table with as many numbers as necessary to represent
- -- its value in base 'RADIX'. It has a field 'len' containing the num-
- -- ber of such numbers and a field 'signal' that may assume the values
- -- '+' and '-'.
- --
- --$.%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- --%%%%%%%% Constants used in the file %%%%%%%%--{{{1
- RADIX = 10^7 ;
- RADIX_LEN = math.floor( math.log10 ( RADIX ) ) ;
- --%%%%%%%% Start of Code %%%%%%%%--
- BigNum = {} ;
- BigNum.mt = {} ;
- --BigNum.new{{{1
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- --
- -- Function: New
- --
- --
- -- Description:
- -- Creates a new Big Number based on the parameter num.
- --
- -- Parameters:
- -- num - a string, number or BigNumber.
- --
- -- Returns:
- -- A Big Number, or a nil value if an error occured.
- --
- --
- -- %%%%%%%% --
- function BigNum.new( num ) --{{{2
- local bignum = {} ;
- setmetatable( bignum , BigNum.mt ) ;
- BigNum.change( bignum , num ) ;
- return bignum ;
- end
- --%%%%%%%%%%%%%%%%%%%% Functions for metatable %%%%%%%%%%%%%%%%%%%%--{{{1
- --BigNum.mt.sub{{{2
- function BigNum.mt.sub( num1 , num2 )
- local temp = BigNum.new() ;
- local bnum1 = BigNum.new( num1 ) ;
- local bnum2 = BigNum.new( num2 ) ;
- BigNum.sub( bnum1 , bnum2 , temp ) ;
- return temp ;
- end
- --BigNum.mt.add{{{2
- function BigNum.mt.add( num1 , num2 )
- local temp = BigNum.new() ;
- local bnum1 = BigNum.new( num1 ) ;
- local bnum2 = BigNum.new( num2 ) ;
- BigNum.add( bnum1 , bnum2 , temp ) ;
- return temp ;
- end
- --BigNum.mt.mul{{{2
- function BigNum.mt.mul( num1 , num2 )
- local temp = BigNum.new() ;
- local bnum1 = BigNum.new( num1 ) ;
- local bnum2 = BigNum.new( num2 ) ;
- BigNum.mul( bnum1 , bnum2 , temp ) ;
- return temp ;
- end
- --BigNum.mt.div{{{2
- function BigNum.mt.div( num1 , num2 )
- local bnum1 = {} ;
- local bnum2 = {} ;
- local bnum3 = BigNum.new() ;
- local bnum4 = BigNum.new() ;
- bnum1 = BigNum.new( num1 ) ;
- bnum2 = BigNum.new( num2 ) ;
- BigNum.div( bnum1 , bnum2 , bnum3 , bnum4 ) ;
- return bnum3 , bnum4 ;
- end
- --BigNum.mt.tostring{{{2
- function BigNum.mt.tostring( bnum )
- local i = 0 ;
- local j = 0 ;
- local str = "" ;
- local temp = "" ;
- if bnum == nil then
- return "nil" ;
- elseif bnum.len > 0 then
- for i = bnum.len - 2 , 0 , -1 do
- for j = 0 , RADIX_LEN - string.len( bnum[i] ) - 1 do
- temp = temp .. '0' ;
- end
- temp = temp .. bnum[i] ;
- end
- temp = bnum[bnum.len - 1] .. temp ;
- if bnum.signal == '-' then
- temp = bnum.signal .. temp ;
- end
- return temp ;
- else
- return "" ;
- end
- end
- --BigNum.mt.pow{{{2
- function BigNum.mt.pow( num1 , num2 )
- local bnum1 = BigNum.new( num1 ) ;
- local bnum2 = BigNum.new( num2 ) ;
- return BigNum.pow( bnum1 , bnum2 ) ;
- end
- --BigNum.mt.eq{{{2
- function BigNum.mt.eq( num1 , num2 )
- local bnum1 = BigNum.new( num1 ) ;
- local bnum2 = BigNum.new( num2 ) ;
- return BigNum.eq( bnum1 , bnum2 ) ;
- end
- --BigNum.mt.lt{{{2
- function BigNum.mt.lt( num1 , num2 )
- local bnum1 = BigNum.new( num1 ) ;
- local bnum2 = BigNum.new( num2 ) ;
- return BigNum.lt( bnum1 , bnum2 ) ;
- end
- --BigNum.mt.le{{{2
- function BigNum.mt.le( num1 , num2 )
- local bnum1 = BigNum.new( num1 ) ;
- local bnum2 = BigNum.new( num2 ) ;
- return BigNum.le( bnum1 , bnum2 ) ;
- end
- --BigNum.mt.unm{{{2
- function BigNum.mt.unm( num )
- local ret = BigNum.new( num )
- if ret.signal == '+' then
- ret.signal = '-'
- else
- ret.signal = '+'
- end
- return ret
- end
- --%%%%%%%%%%%%%%%%%%%% Metatable Definitions %%%%%%%%%%%%%%%%%%%%--{{{1
- BigNum.mt.__metatable = "hidden" ; -- answer to getmetatable(aBignum)
- -- BigNum.mt.__index = "inexistent field" ; -- attempt to acess nil valued field
- -- BigNum.mt.__newindex = "not available" ; -- attempt to create new field
- BigNum.mt.__tostring = BigNum.mt.tostring ;
- -- arithmetics
- BigNum.mt.__add = BigNum.mt.add ;
- BigNum.mt.__sub = BigNum.mt.sub ;
- BigNum.mt.__mul = BigNum.mt.mul ;
- BigNum.mt.__div = BigNum.mt.div ;
- BigNum.mt.__pow = BigNum.mt.pow ;
- BigNum.mt.__unm = BigNum.mt.unm ;
- -- Comparisons
- BigNum.mt.__eq = BigNum.mt.eq ;
- BigNum.mt.__le = BigNum.mt.le ;
- BigNum.mt.__lt = BigNum.mt.lt ;
- --concatenation
- -- BigNum.me.__concat = ???
- setmetatable( BigNum.mt, { __index = "inexistent field", __newindex = "not available", __metatable="hidden" } ) ;
- --%%%%%%%%%%%%%%%%%%%% Basic Functions %%%%%%%%%%%%%%%%%%%%--{{{1
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: ADD
- --
- --
- -- Description:
- -- Adds two Big Numbers.
- --
- -- Parameters:
- -- bnum1, bnum2 - Numbers to be added.
- -- bnum3 - result
- --
- -- Returns:
- -- 0
- --
- -- Exit assertions:
- -- bnum3 is the result of the sum.
- --
- -- %%%%%%%% --
- --Funcao BigNum.add{{{2
- function BigNum.add( bnum1 , bnum2 , bnum3 )
- local maxlen = 0 ;
- local i = 0 ;
- local carry = 0 ;
- local signal = '+' ;
- local old_len = 0 ;
- --Handle the signals
- if bnum1 == nil or bnum2 == nil or bnum3 == nil then
- error("Function BigNum.add: parameter nil") ;
- elseif bnum1.signal == '-' and bnum2.signal == '+' then
- bnum1.signal = '+' ;
- BigNum.sub( bnum2 , bnum1 , bnum3 ) ;
- if not rawequal(bnum1, bnum3) then
- bnum1.signal = '-' ;
- end
- return 0 ;
- elseif bnum1.signal == '+' and bnum2.signal == '-' then
- bnum2.signal = '+' ;
- BigNum.sub( bnum1 , bnum2 , bnum3 ) ;
- if not rawequal(bnum2, bnum3) then
- bnum2.signal = '-' ;
- end
- return 0 ;
- elseif bnum1.signal == '-' and bnum2.signal == '-' then
- signal = '-' ;
- end
- --
- old_len = bnum3.len ;
- if bnum1.len > bnum2.len then
- maxlen = bnum1.len ;
- else
- maxlen = bnum2.len ;
- bnum1 , bnum2 = bnum2 , bnum1 ;
- end
- --School grade sum
- for i = 0 , maxlen - 1 do
- if bnum2[i] ~= nil then
- bnum3[i] = bnum1[i] + bnum2[i] + carry ;
- else
- bnum3[i] = bnum1[i] + carry ;
- end
- if bnum3[i] >= RADIX then
- bnum3[i] = bnum3[i] - RADIX ;
- carry = 1 ;
- else
- carry = 0 ;
- end
- end
- --Update the answer's size
- if carry == 1 then
- bnum3[maxlen] = 1 ;
- end
- bnum3.len = maxlen + carry ;
- bnum3.signal = signal ;
- for i = bnum3.len, old_len do
- bnum3[i] = nil ;
- end
- return 0 ;
- end
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: SUB
- --
- --
- -- Description:
- -- Subtracts two Big Numbers.
- --
- -- Parameters:
- -- bnum1, bnum2 - Numbers to be subtracted.
- -- bnum3 - result
- --
- -- Returns:
- -- 0
- --
- -- Exit assertions:
- -- bnum3 is the result of the subtraction.
- --
- -- %%%%%%%% --
- --Funcao BigNum.sub{{{2
- function BigNum.sub( bnum1 , bnum2 , bnum3 )
- local maxlen = 0 ;
- local i = 0 ;
- local carry = 0 ;
- local old_len = 0 ;
- --Handle the signals
- if bnum1 == nil or bnum2 == nil or bnum3 == nil then
- error("Function BigNum.sub: parameter nil") ;
- elseif bnum1.signal == '-' and bnum2.signal == '+' then
- bnum1.signal = '+' ;
- BigNum.add( bnum1 , bnum2 , bnum3 ) ;
- bnum3.signal = '-' ;
- if not rawequal(bnum1, bnum3) then
- bnum1.signal = '-' ;
- end
- return 0 ;
- elseif bnum1.signal == '-' and bnum2.signal == '-' then
- bnum1.signal = '+' ;
- bnum2.signal = '+' ;
- BigNum.sub( bnum2, bnum1 , bnum3 ) ;
- if not rawequal(bnum1, bnum3) then
- bnum1.signal = '-' ;
- end
- if not rawequal(bnum2, bnum3) then
- bnum2.signal = '-' ;
- end
- return 0 ;
- elseif bnum1.signal == '+' and bnum2.signal == '-' then
- bnum2.signal = '+' ;
- BigNum.add( bnum1 , bnum2 , bnum3 ) ;
- if not rawequal(bnum2, bnum3) then
- bnum2.signal = '-' ;
- end
- return 0 ;
- end
- --Tests if bnum2 > bnum1
- if BigNum.compareAbs( bnum1 , bnum2 ) == 2 then
- BigNum.sub( bnum2 , bnum1 , bnum3 ) ;
- bnum3.signal = '-' ;
- return 0 ;
- else
- maxlen = bnum1.len ;
- end
- old_len = bnum3.len ;
- bnum3.len = 0 ;
- --School grade subtraction
- for i = 0 , maxlen - 1 do
- if bnum2[i] ~= nil then
- bnum3[i] = bnum1[i] - bnum2[i] - carry ;
- else
- bnum3[i] = bnum1[i] - carry ;
- end
- if bnum3[i] < 0 then
- bnum3[i] = RADIX + bnum3[i] ;
- carry = 1 ;
- else
- carry = 0 ;
- end
- if bnum3[i] ~= 0 then
- bnum3.len = i + 1 ;
- end
- end
- bnum3.signal = '+' ;
- --Check if answer's size if zero
- if bnum3.len == 0 then
- bnum3.len = 1 ;
- bnum3[0] = 0 ;
- end
- if carry == 1 then
- error( "Error in function sub" ) ;
- end
- for i = bnum3.len , max( old_len , maxlen - 1 ) do
- bnum3[i] = nil ;
- end
- return 0 ;
- end
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: MUL
- --
- --
- -- Description:
- -- Multiplies two Big Numbers.
- --
- -- Parameters:
- -- bnum1, bnum2 - Numbers to be multiplied.
- -- bnum3 - result
- --
- -- Returns:
- -- 0
- --
- -- Exit assertions:
- -- bnum3 is the result of the multiplication.
- --
- -- %%%%%%%% --
- --BigNum.mul{{{2
- --can't be made in place
- function BigNum.mul( bnum1 , bnum2 , bnum3 )
- local i = 0 ; j = 0 ;
- local temp = BigNum.new( ) ;
- local temp2 = 0 ;
- local carry = 0 ;
- local oldLen = bnum3.len ;
- if bnum1 == nil or bnum2 == nil or bnum3 == nil then
- error("Function BigNum.mul: parameter nil") ;
- --Handle the signals
- elseif bnum1.signal ~= bnum2.signal then
- BigNum.mul( bnum1 , -bnum2 , bnum3 ) ;
- bnum3.signal = '-' ;
- return 0 ;
- end
- bnum3.len = ( bnum1.len ) + ( bnum2.len ) ;
- --Fill with zeros
- for i = 1 , bnum3.len do
- bnum3[i - 1] = 0 ;
- end
- --Places nil where passes through this
- for i = bnum3.len , oldLen do
- bnum3[i] = nil ;
- end
- --School grade multiplication
- for i = 0 , bnum1.len - 1 do
- for j = 0 , bnum2.len - 1 do
- carry = ( bnum1[i] * bnum2[j] + carry ) ;
- carry = carry + bnum3[i + j] ;
- bnum3[i + j] = ( carry % RADIX ) ;
- temp2 = bnum3[i + j] ;
- carry = math.floor ( carry / RADIX ) ;
- end
- if carry ~= 0 then
- bnum3[i + bnum2.len] = carry ;
- end
- carry = 0 ;
- end
- --Update the answer's size
- for i = bnum3.len - 1 , 1 , -1 do
- if bnum3[i] ~= nil and bnum3[i] ~= 0 then
- break ;
- else
- bnum3[i] = nil ;
- end
- bnum3.len = bnum3.len - 1 ;
- end
- return 0 ;
- end
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: DIV
- --
- --
- -- Description:
- -- Divides bnum1 by bnum2.
- --
- -- Parameters:
- -- bnum1, bnum2 - Numbers to be divided.
- -- bnum3 - result
- -- bnum4 - remainder
- --
- -- Returns:
- -- 0
- --
- -- Exit assertions:
- -- bnum3 is the result of the division.
- -- bnum4 is the remainder of the division.
- --
- -- %%%%%%%% --
- --BigNum.div{{{2
- function BigNum.div( bnum1 , bnum2 , bnum3 , bnum4 )
- local temp = BigNum.new() ;
- local temp2 = BigNum.new() ;
- local one = BigNum.new( "1" ) ;
- local zero = BigNum.new( "0" ) ;
- --Check division by zero
- if BigNum.compareAbs( bnum2 , zero ) == 0 then
- error( "Function BigNum.div: Division by zero" ) ;
- end
- --Handle the signals
- if bnum1 == nil or bnum2 == nil or bnum3 == nil or bnum4 == nil then
- error( "Function BigNum.div: parameter nil" ) ;
- elseif bnum1.signal == "+" and bnum2.signal == "-" then
- bnum2.signal = "+" ;
- BigNum.div( bnum1 , bnum2 , bnum3 , bnum4 ) ;
- bnum2.signal = "-" ;
- bnum3.signal = "-" ;
- return 0 ;
- elseif bnum1.signal == "-" and bnum2.signal == "+" then
- bnum1.signal = "+" ;
- BigNum.div( bnum1 , bnum2 , bnum3 , bnum4 ) ;
- bnum1.signal = "-" ;
- if bnum4 < zero then --Check if remainder is negative
- BigNum.add( bnum3 , one , bnum3 ) ;
- BigNum.sub( bnum2 , bnum4 , bnum4 ) ;
- end
- bnum3.signal = "-" ;
- return 0 ;
- elseif bnum1.signal == "-" and bnum2.signal == "-" then
- bnum1.signal = "+" ;
- bnum2.signal = "+" ;
- BigNum.div( bnum1 , bnum2 , bnum3 , bnum4 ) ;
- bnum1.signal = "-" ;
- if bnum4 < zero then --Check if remainder is negative
- BigNum.add( bnum3 , one , bnum3 ) ;
- BigNum.sub( bnum2 , bnum4 , bnum4 ) ;
- end
- bnum2.signal = "-" ;
- return 0 ;
- end
- temp.len = bnum1.len - bnum2.len - 1 ;
- --Reset variables
- BigNum.change( bnum3 , "0" ) ;
- BigNum.change( bnum4 , "0" ) ;
- BigNum.copy( bnum1 , bnum4 ) ;
- --Check if can continue dividing
- while( BigNum.compareAbs( bnum4 , bnum2 ) ~= 2 ) do
- if bnum4[bnum4.len - 1] >= bnum2[bnum2.len - 1] then
- BigNum.put( temp , math.floor( bnum4[bnum4.len - 1] / bnum2[bnum2.len - 1] ) , bnum4.len - bnum2.len ) ;
- temp.len = bnum4.len - bnum2.len + 1 ;
- else
- BigNum.put( temp , math.floor( ( bnum4[bnum4.len - 1] * RADIX + bnum4[bnum4.len - 2] ) / bnum2[bnum2.len -1] ) , bnum4.len - bnum2.len - 1 ) ;
- temp.len = bnum4.len - bnum2.len ;
- end
- if bnum4.signal ~= bnum2.signal then
- temp.signal = "-";
- else
- temp.signal = "+";
- end
- BigNum.add( temp , bnum3 , bnum3 ) ;
- temp = temp * bnum2 ;
- BigNum.sub( bnum4 , temp , bnum4 ) ;
- end
- --Update if the remainder is negative
- if bnum4.signal == '-' then
- decr( bnum3 ) ;
- BigNum.add( bnum2 , bnum4 , bnum4 ) ;
- end
- return 0 ;
- end
- --%%%%%%%%%%%%%%%%%%%% Compound Functions %%%%%%%%%%%%%%%%%%%%--{{{1
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: POW / EXP
- --
- --
- -- Description:
- -- Computes a big number which represents the bnum2-th power of bnum1.
- --
- -- Parameters:
- -- bnum1 - base
- -- bnum2 - expoent
- --
- -- Returns:
- -- Returns a big number which represents the bnum2-th power of bnum1.
- --
- -- %%%%%%%% --
- --BigNum.exp{{{2
- function BigNum.pow( bnum1 , bnum2 )
- local n = BigNum.new( bnum2 ) ;
- local y = BigNum.new( 1 ) ;
- local z = BigNum.new( bnum1 ) ;
- local zero = BigNum.new( "0" ) ;
- if bnum2 < zero then
- error( "Function BigNum.exp: domain error" ) ;
- elseif bnum2 == zero then
- return y ;
- end
- while 1 do
- if( n[0]% 2 ) == 0 then
- n = n / 2 ;
- else
- n = n / 2 ;
- y = z * y ;
- if n == zero then
- return y ;
- end
- end
- z = z * z ;
- end
- end
- -- Portuguкs :
- BigNum.exp = BigNum.pow
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: GCD / MMC
- --
- --
- -- Description:
- -- Computes the greatest commom divisor of bnum1 and bnum2.
- --
- -- Parameters:
- -- bnum1, bnum2 - positive numbers
- --
- -- Returns:
- -- Returns a big number witch represents the gcd between bnum1 and bnum2.
- --
- -- %%%%%%%% --
- --BigNum.gcd{{{2
- function BigNum.gcd( bnum1 , bnum2 )
- local a = {} ;
- local b = {} ;
- local c = {} ;
- local d = {} ;
- local zero = {} ;
- zero = BigNum.new( "0" ) ;
- if bnum1 == zero or bnum2 == zero then
- return BigNum.new( "1" ) ;
- end
- a = BigNum.new( bnum1 ) ;
- b = BigNum.new( bnum2 ) ;
- a.signal = '+' ;
- b.signal = '+' ;
- c = BigNum.new() ;
- d = BigNum.new() ;
- while b > zero do
- BigNum.div( a , b , c , d ) ;
- a , b , d = b , d , a ;
- end
- return a ;
- end
- -- Portuguкs:
- BigNum.mmc = BigNum.gcd
- --%%%%%%%%%%%%%%%%%%%% Comparison Functions %%%%%%%%%%%%%%%%%%%%--{{{1
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: EQ
- --
- --
- -- Description:
- -- Compares two Big Numbers.
- --
- -- Parameters:
- -- bnum1, bnum2 - numbers
- --
- -- Returns:
- -- Returns true if they are equal or false otherwise.
- --
- -- %%%%%%%% --
- --BigNum.eq{{{2
- function BigNum.eq( bnum1 , bnum2 )
- if BigNum.compare( bnum1 , bnum2 ) == 0 then
- return true ;
- else
- return false ;
- end
- end
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: LT
- --
- --
- -- Description:
- -- Verifies if bnum1 is lesser than bnum2.
- --
- -- Parameters:
- -- bnum1, bnum2 - numbers
- --
- -- Returns:
- -- Returns true if bnum1 is lesser than bnum2 or false otherwise.
- --
- -- %%%%%%%% --
- --BigNum.lt{{{2
- function BigNum.lt( bnum1 , bnum2 )
- if BigNum.compare( bnum1 , bnum2 ) == 2 then
- return true ;
- else
- return false ;
- end
- end
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: LE
- --
- --
- -- Description:
- -- Verifies if bnum1 is lesser or equal than bnum2.
- --
- -- Parameters:
- -- bnum1, bnum2 - numbers
- --
- -- Returns:
- -- Returns true if bnum1 is lesser or equal than bnum2 or false otherwise.
- --
- -- %%%%%%%% --
- --BigNum.le{{{2
- function BigNum.le( bnum1 , bnum2 )
- local temp = -1 ;
- temp = BigNum.compare( bnum1 , bnum2 )
- if temp == 0 or temp == 2 then
- return true ;
- else
- return false ;
- end
- end
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: Compare Absolute Values
- --
- --
- -- Description:
- -- Compares absolute values of bnum1 and bnum2.
- --
- -- Parameters:
- -- bnum1, bnum2 - numbers
- --
- -- Returns:
- -- 1 - |bnum1| > |bnum2|
- -- 2 - |bnum1| < |bnum2|
- -- 0 - |bnum1| = |bnum2|
- --
- -- %%%%%%%% --
- --BigNum.compareAbs{{{2
- function BigNum.compareAbs( bnum1 , bnum2 )
- if bnum1 == nil or bnum2 == nil then
- error("Function compare: parameter nil") ;
- elseif bnum1.len > bnum2.len then
- return 1 ;
- elseif bnum1.len < bnum2.len then
- return 2 ;
- else
- local i ;
- for i = bnum1.len - 1 , 0 , -1 do
- if bnum1[i] > bnum2[i] then
- return 1 ;
- elseif bnum1[i] < bnum2[i] then
- return 2 ;
- end
- end
- end
- return 0 ;
- end
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: Compare
- --
- --
- -- Description:
- -- Compares values of bnum1 and bnum2.
- --
- -- Parameters:
- -- bnum1, bnum2 - numbers
- --
- -- Returns:
- -- 1 - |bnum1| > |bnum2|
- -- 2 - |bnum1| < |bnum2|
- -- 0 - |bnum1| = |bnum2|
- --
- -- %%%%%%%% --
- --BigNum.compare{{{2
- function BigNum.compare( bnum1 , bnum2 )
- local signal = 0 ;
- if bnum1 == nil or bnum2 == nil then
- error("Funtion BigNum.compare: parameter nil") ;
- elseif bnum1.signal == '+' and bnum2.signal == '-' then
- return 1 ;
- elseif bnum1.signal == '-' and bnum2.signal == '+' then
- return 2 ;
- elseif bnum1.signal == '-' and bnum2.signal == '-' then
- signal = 1 ;
- end
- if bnum1.len > bnum2.len then
- return 1 + signal ;
- elseif bnum1.len < bnum2.len then
- return 2 - signal ;
- else
- local i ;
- for i = bnum1.len - 1 , 0 , -1 do
- if bnum1[i] > bnum2[i] then
- return 1 + signal ;
- elseif bnum1[i] < bnum2[i] then
- return 2 - signal ;
- end
- end
- end
- return 0 ;
- end
- --%%%%%%%%%%%%%%%%%%%% Low level Functions %%%%%%%%%%%%%%%%%%%%--{{{1
- --BigNum.copy{{{2
- function BigNum.copy( bnum1 , bnum2 )
- if bnum1 ~= nil and bnum2 ~= nil then
- local i ;
- for i = 0 , bnum1.len - 1 do
- bnum2[i] = bnum1[i] ;
- end
- bnum2.len = bnum1.len ;
- else
- error("Function BigNum.copy: parameter nil") ;
- end
- end
- --%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%{{{2
- --
- -- Function: Change
- --
- -- Description:
- -- Changes the value of a BigNum.
- -- This function is called by BigNum.new.
- --
- -- Parameters:
- -- bnum1, bnum2 - numbers
- --
- -- Returns:
- -- 1 - |bnum1| > |bnum2|
- -- 2 - |bnum1| < |bnum2|
- -- 0 - |bnum1| = |bnum2|
- --
- -- %%%%%%%% --
- --BigNum.change{{{2
- function BigNum.change( bnum1 , num )
- local j = 0 ;
- local len = 0 ;
- local num = num ;
- local l ;
- local oldLen = 0 ;
- if bnum1 == nil then
- error( "BigNum.change: parameter nil" ) ;
- elseif type( bnum1 ) ~= "table" then
- error( "BigNum.change: parameter error, type unexpected" ) ;
- elseif num == nil then
- bnum1.len = 1 ;
- bnum1[0] = 0 ;
- bnum1.signal = "+";
- elseif type( num ) == "table" and num.len ~= nil then --check if num is a big number
- --copy given table to the new one
- for i = 0 , num.len do
- bnum1[i] = num[i] ;
- end
- if num.signal ~= '-' and num.signal ~= '+' then
- bnum1.signal = '+' ;
- else
- bnum1.signal = num.signal ;
- end
- oldLen = bnum1.len ;
- bnum1.len = num.len ;
- elseif type( num ) == "string" or type( num ) == "number" then
- if string.sub( num , 1 , 1 ) == '+' or string.sub( num , 1 , 1 ) == '-' then
- bnum1.signal = string.sub( num , 1 , 1 ) ;
- num = string.sub(num, 2) ;
- else
- bnum1.signal = '+' ;
- end
- num = string.gsub( num , " " , "" ) ;
- local sf = string.find( num , "e" ) ;
- --Handles if the number is in exp notation
- if sf ~= nil then
- num = string.gsub( num , "%." , "" ) ;
- local e = string.sub( num , sf + 1 ) ;
- e = tonumber(e) ;
- if e ~= nil and e > 0 then
- e = tonumber(e) ;
- else
- error( "Function BigNum.change: string is not a valid number" ) ;
- end
- num = string.sub( num , 1 , sf - 2 ) ;
- for i = string.len( num ) , e do
- num = num .. "0" ;
- end
- else
- sf = string.find( num , "%." ) ;
- if sf ~= nil then
- num = string.sub( num , 1 , sf - 1 ) ;
- end
- end
- l = string.len( num ) ;
- oldLen = bnum1.len ;
- if (l > RADIX_LEN) then
- local mod = l-( math.floor( l / RADIX_LEN ) * RADIX_LEN ) ;
- for i = 1 , l-mod, RADIX_LEN do
- bnum1[j] = tonumber( string.sub( num, -( i + RADIX_LEN - 1 ) , -i ) );
- --Check if string dosn't represents a number
- if bnum1[j] == nil then
- error( "Function BigNum.change: string is not a valid number" ) ;
- bnum1.len = 0 ;
- return 1 ;
- end
- j = j + 1 ;
- len = len + 1 ;
- end
- if (mod ~= 0) then
- bnum1[j] = tonumber( string.sub( num , 1 , mod ) ) ;
- bnum1.len = len + 1 ;
- else
- bnum1.len = len ;
- end
- --Eliminate trailing zeros
- for i = bnum1.len - 1 , 1 , -1 do
- if bnum1[i] == 0 then
- bnum1[i] = nil ;
- bnum1.len = bnum1.len - 1 ;
- else
- break ;
- end
- end
- else
- -- string.len(num) <= RADIX_LEN
- bnum1[j] = tonumber( num ) ;
- bnum1.len = 1 ;
- end
- else
- error( "Function BigNum.change: parameter error, type unexpected" ) ;
- end
- --eliminates the deprecated higher order 'algarisms'
- if oldLen ~= nil then
- for i = bnum1.len , oldLen do
- bnum1[i] = nil ;
- end
- end
- return 0 ;
- end
- --BigNum.put{{{2
- --Places int in the position pos of bignum, fills before with zeroes and
- --after with nil.
- function BigNum.put( bnum , int , pos )
- if bnum == nil then
- error("Function BigNum.put: parameter nil") ;
- end
- local i = 0 ;
- for i = 0 , pos - 1 do
- bnum[i] = 0 ;
- end
- bnum[pos] = int ;
- for i = pos + 1 , bnum.len do
- bnum[i] = nil ;
- end
- bnum.len = pos ;
- return 0 ;
- end
- --printraw{{{2
- function printraw( bnum )
- local i = 0 ;
- if bnum == nil then
- error( "Function printraw: parameter nil" ) ;
- end
- while 1 == 1 do
- if bnum[i] == nil then
- io.write( ' len '..bnum.len ) ;
- if i ~= bnum.len then
- io.write( ' ERRO!!!!!!!!' ) ;
- end
- io.write( "\n" ) ;
- return 0 ;
- end
- io.write( 'r'..bnum[i] ) ;
- i = i + 1 ;
- end
- end
- --max{{{2
- function max( int1 , int2 )
- if int1 > int2 then
- return int1 ;
- else
- return int2 ;
- end
- end
- --decr{{{2
- function decr( bnum1 )
- local temp = {} ;
- temp = BigNum.new( "1" ) ;
- BigNum.sub( bnum1 , temp , bnum1 ) ;
- return 0 ;
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement