- Joined
- Jul 10, 2007
- Messages
- 6,306
if (e[n[y]]) then
set n[y] = n[0]
set n[0] = y
set y = p[y]
set p[td] = y
set n[y] = td
else
set y = p[y]
endif
Not really ;D.does it make sense to use them for numbers with a maximum of 500-200000?
Actually, performing arithmetic on an integer would be much slower than looping through a list.
method multiply takes integer value, integer exponent returns nothing
method multiply takes integer value returns nothing
method toInt takes nothing returns integer
method mod takes integer k returns integer
method rl takes nothing returns nothing
method rr takes nothing returns nothing
struct tester extends array
private static method onInit takes nothing returns nothing
/*//mod demo
local BigInt int = BigInt.create(Base["0123456789"])
call int.add(12923,0)
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "11==" + I2S(int.mod(16)))
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "5==" + I2S(int.mod(6)))
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "471==" + I2S(int.mod(566)))
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "98==" + I2S(int.mod(225)))
*/
//rotate demo
local BigInt int = BigInt.create(Base["0123456789"])
call int.add(123456789,0)
//rotate left
call int.rl()
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "912345678==" + I2S(int.toInt()))
//rotate left
call int.rl()
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "891234567==" + I2S(int.toInt()))
//rotate right
call int.rr()
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "912345678==" + I2S(int.toInt()))
//rotate right
call int.rr()
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "123456789==" + I2S(int.toInt()))
endmethod
endstruct
method addBig takes BigInt k returns nothing
method multiplyBig takes BigInt k returns nothing
method copy takes nothing returns BigInt
struct tester extends array
private static method onInit takes nothing returns nothing
/*//copy demo
local BigInt int = BigInt.create(Base["0123456789"])
local BigInt copy
call int.add(194382,3)
call int.multiply(204202)
call int.add(2482,10)
set copy = int.copy()
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, int.toString() + "==\n" + copy.toString())
*/
/*//multiply big demo
local BigInt int = BigInt.create(Base["0123456789"])
local BigInt int2 = BigInt.create(Base["0123456789"])
call int.add(3429201,0)
call int2.add(5942242,0)
call int2.add(793483,8)
call int.multiplyBig(int2)
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "272101290085442208642==\n" + int.toString())
*/
/*//add big demo
local BigInt int = BigInt.create(Base["0123456789"])
local BigInt int2 = BigInt.create(Base["0123456789"])
call int.add(3429201,0)
call int2.add(5942242,0)
call int2.add(793483,8)
call int.addBig(int2,3)
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "79348305945671201==\n" + int.toString())
*/
endmethod
endstruct
I wrote a fractions module in JASS, check the graveyard
Except, it takes BigInt and power. *tsk tsk*//method addBig takes BigInt k returns nothing
By any chance, do you have pseudo code for this? x)
The method you show in the article is archaic. There is a MUCH more efficient algorithm. (This is the algorithm actually used behind the scenes inside a calculator when you hit the square root button.)
1. Estimate the square root to at least 1 digit.
2. Divide this estimate into the number whose square root you want to find.
3. Find the average of the quotient and the divisor. The result becomes the new estimate.
The beauty of this method is that the accuracy of the estimate grows extremely rapidly. Each cycle will essentially double the number of correct digits. From a 1-digit starting point you can get a 4-digit result in two cycles. If you know a square root already to a few digits, such as sqrt(2)=1.414, a single cycle of divide and average will give you double the digits (eight, in this case).
In addition to giving a way to find square roots by hand, this method can be used if all you have is a cheap 4-function calculator. If students can get square roots manually, they will not find square roots to be so mysterious. Also, this method is a good first example of an itterative solution of a problem.
David Chandler
This other way is called Babylonian method of guess and divide, and it truly is faster. It is also the same as you would get applying Newton's method. See for example finding the square root of 20 using 10 as the initial guess:
Code:Guess Divide Find average 10 20/10 = 2 average 10 and 2 to give new guess of 6 6 20/6 = 3.333 average 3.333 and 6 gives 4.6666 4.666 20/4.666= 4.1414 average 4.666,4.1414= 4.4048 4.4048 20/4.4048=4.5454 average = 4.4700 4.4700 20/4.4700=4.4742 average = 4.4721 4.4721 20/4.4721=4.47217 average = 4.47214 This is already to 4 decimal places
Eh, I'm not writing that... you write it and I'll add it in and give your credit : P
float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
}
function SquareRootX takes real number returns real
local real x = number * 0.5
local real y = number
local real f = 1.5
local integer i = R2I(y)
if i < 1 then
set i = 1
endif
set i = 0x5f3759df - i
set y = i
set y = y * ( f - ( x * y * y ) )
set y = y * ( f - ( x * y * y ) )
return number * y
endfunction
function SquareRootX takes real number returns real
local real x = number * 0.5
local real y = number
local integer i = R2I(y)
if i < 1 then
set y = 0x5f3759de
else
set y = 0x5f3759df - i
endif
set y = y * (1.5 - x * y * y)
return number * y * (1.5 - x * y * y)
endfunction
struct testers extends array
private static method init takes nothing returns nothing
local BigInt2 i = BigInt2.create()
local Base b80 = Base["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!@#$%^&*()-_+=~?><"]
local integer b = 26
call i.add(2147483647)
loop
set b = b - 1
exitwhen b == 0
call i.multiply(2147483647)
endloop
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,i.toString(b80))
call DestroyTimer(GetExpiredTimer())
endmethod
private static method onInit takes nothing returns nothing
call TimerStart(CreateTimer(),0,false,function thistype.init)
endmethod
endstruct
private static method multiply2 takes nothing returns boolean
local integer this = toBeMultiplied
local integer d = this
local integer i = toMultiply
local integer t
local integer array db
local integer dbc = 0
local integer s = 0
local integer m = 0
local integer k
loop
exitwhen 0 == i
set t = i - i/46340*46340
set i = i/46340
set m = m + 1
set s = m - 1
loop
set d = n[d]
exitwhen h[d]
set s = s + 1
set db[s] = db[s] + v[d]*t
set k = s - 1
loop
set k = k + 1
exitwhen 46340 > db[k]
set db[k+1] = db[k+1] + db[k]/46340
set db[k] = db[k] - db[k]/46340*46340
endloop
if (dbc < k) then
set dbc = k
endif
endloop
if (dbc < s) then
set dbc = s
endif
endloop
if (dbc < m) then
set dbc = m
endif
loop
set d = p[d]
if (h[d]) then
set d = n[0]
if (0 == d) then
set d = ic + 1
set ic = d
else
set n[0] = d
endif
set p[d] = this
set n[d] = n[this]
set p[n[this]] = d
set n[this] = d
endif
set v[d] = db[dbc]
set dbc = dbc - 1
exitwhen 0 == dbc
endloop
return true
endmethod
2^31-1 * 46340
1 0
1 1
41707 0
x = 46340
x + 1 + 41707/x
x x^2+x+41707
x^2
0-x
0-41707
x+1 r41707
(46340+1)*46340+41707 = 2^31-1
private static method toString2 takes nothing returns boolean
//Base toBase base
//BigInt toStr BigInt being converted to string
//string returnStr string to return
local integer size = toBase.size //base size
local integer ii = 0 //op count
local integer d = toStr //divide BigInt
local integer m = 0 //remainder
local integer cc = 0 //calc next op limit
//op limit loop
loop
set cc = 0
//division loop
loop
//division gather numbers to divide
if (m < size) then
loop
set d = p[d] //go to prev digit
exitwhen h[d]
set cc = cc + 2
//exitwhen remainder (numbers being pulled out of BigInt) is bigger than number doing the dividing
set m = m*BASE + v[d]
exitwhen m >= size
//! runtextmacro BIG_INT_REMOVE("d")
//! runtextmacro BIG_INT_DEALLOCATE("d")
set cc = cc + 9
endloop
endif
set cc = cc + 2
exitwhen h[d]
//in this case, remaining digits will always be < base
//! runtextmacro BIG_INT_GET_REMAINING_DIGITS("v[d]", "m", "size")
//! runtextmacro BIG_INT_GET_CURRENT_DIGIT("m", "m", "size")
set cc = cc + 4
endloop
set returnStr = toBase.char(m) + returnStr
exitwhen h[n[toStr]]
set m = 0
set cc = cc + 2
set ii = ii + cc
if (ii > 23000) then
return false
endif
endloop
return true
endmethod
method toString takes Base base returns string
//if BigInt isn't empty
if (not h[n[this]]) then
set this = copy()
set toBase = base
set toStr = this
set returnStr = ""
//loop until done converting
loop
exitwhen TriggerEvaluate(strt)
endloop
return returnStr
endif
return base.char(0)
endmethod
set cc = 0
to the end of the first loop in your toString2 function ;Pset cc = cc + 2
set ii = ii + cc
set ii = ii + cc + 2
set m = m*BASE + v[d]