- Joined
- Jul 10, 2007
- Messages
- 6,306
What is 83/19?
1. Divide first digits
[8]3/[1]9
8/1 = 8
2. Subtract second digit * guess
If second digit >= base/2, subtract second digit * guess * 1/2 + 1
83/1[9]
Guess: 8
9*8 = [7]2
9 >= 10/2
7/2 = 3 + 1 = 4
8 - 4 = 4
3. Multiply by guess
19*4 = 76
4. Subtract
83-76 = 7
5. Repeat until remainder < divisor
7 < 19
Answer: 4 r7
With this, I can now go back to BigInt v2 ;D
edit
1 snag in the algorithm, but fixed it
If the initial guess is 0, do first 2 digits of dividend divided by first digit of divisor. From there, instead of subtracting first digit of product guess*2nd last digit, do product/first 2 digits of dividend. Appears to work perfectly.
edit
Ok, here is the library. If anyone could try out a variety of numbers to make sure I got all of the bugs, I'd really appreciate it ^)^. Just make sure the output is what it's supposed to be.
You can't add/divide/multiply/subtract numbers of different bases, so if you purposefully make the 2 numbers different bases, it won't work. I haven't done stuff to avoid op limit in this yet, so if you don't see the messages, don't whine about it because I already know. Please use base 32768 as higher bases have less accuracy for guessing ^)^. The current numbers in there do in fact give out correct results.
Do not check the results against microsoft's calculator as BigInt is more accurate >.<, meaning you will get strange things for large numbers. Use this site instead -> http://world.std.com/~reinhold/BigNumCalc.html
Anyways, as soon as I write some docs, make this work off of Base, and add a few more features, this'll be ready for release given nobody gets bad output ;D. Oh, and if you take a look, the multiply algorithm is actually a lot faster than it used to be ; P. And yes, this division algorithm is 100% reliable, 0 chance of overflow, fuahahahah ;D.
Oh yea, and this is still totally unsigned... signed bit ints for wc3 are totally pointless >.<.
1. Divide first digits
[8]3/[1]9
8/1 = 8
2. Subtract second digit * guess
If second digit >= base/2, subtract second digit * guess * 1/2 + 1
83/1[9]
Guess: 8
9*8 = [7]2
9 >= 10/2
7/2 = 3 + 1 = 4
8 - 4 = 4
3. Multiply by guess
19*4 = 76
4. Subtract
83-76 = 7
5. Repeat until remainder < divisor
7 < 19
Answer: 4 r7
With this, I can now go back to BigInt v2 ;D
edit
1 snag in the algorithm, but fixed it
If the initial guess is 0, do first 2 digits of dividend divided by first digit of divisor. From there, instead of subtracting first digit of product guess*2nd last digit, do product/first 2 digits of dividend. Appears to work perfectly.
edit
Ok, here is the library. If anyone could try out a variety of numbers to make sure I got all of the bugs, I'd really appreciate it ^)^. Just make sure the output is what it's supposed to be.
You can't add/divide/multiply/subtract numbers of different bases, so if you purposefully make the 2 numbers different bases, it won't work. I haven't done stuff to avoid op limit in this yet, so if you don't see the messages, don't whine about it because I already know. Please use base 32768 as higher bases have less accuracy for guessing ^)^. The current numbers in there do in fact give out correct results.
Do not check the results against microsoft's calculator as BigInt is more accurate >.<, meaning you will get strange things for large numbers. Use this site instead -> http://world.std.com/~reinhold/BigNumCalc.html
Anyways, as soon as I write some docs, make this work off of Base, and add a few more features, this'll be ready for release given nobody gets bad output ;D. Oh, and if you take a look, the multiply algorithm is actually a lot faster than it used to be ; P. And yes, this division algorithm is 100% reliable, 0 chance of overflow, fuahahahah ;D.
Oh yea, and this is still totally unsigned... signed bit ints for wc3 are totally pointless >.<.
JASS:
//! textmacro TEST
struct Tester extends array
private static method init takes nothing returns nothing
local string dividendV = "120043923300"
local string divisorV = "15339"
local BigInt remainder
local BigInt dividend = BigInt.convertString(dividendV, 32768)
local BigInt divisor = BigInt.convertString(divisorV, 32768)
call DestroyTimer(GetExpiredTimer())
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"Divisor: " + divisorV + " == " + divisor.toString())
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"Dividend: " + dividendV + " == " + dividend.toString())
//call divisor.addBig(dividend)
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,divisor.toString())
set remainder = dividend.divide(divisor)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"Divided: "+dividend.toString())
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"Remainder: "+remainder.toString())
endmethod
private static method onInit takes nothing returns nothing
call TimerStart(CreateTimer(), 0, false, function thistype.init)
endmethod
endstruct
//! endtextmacro
library BigInt
private struct BigInt extends array
readonly thistype next
readonly thistype prev
integer digit
readonly boolean head
readonly integer base
private static integer count = 0
private static method allocate takes nothing returns thistype
local thistype this = thistype(0).next
if (0 == this) then
set this = count + 1
set count = this
else
set thistype(0).next = next
endif
set digit = 0
return this
endmethod
private method ad takes thistype n returns nothing
set n.next = this
set n.prev = prev
set prev.next = n
set prev = n
endmethod
private method adp takes thistype n returns nothing
set n.next = next
set n.prev = this
set next.prev = n
set next = n
endmethod
private method carryOver takes thistype root, integer carry, integer base returns nothing
loop
exitwhen 0 == carry
set this = next
if (head) then
set this = allocate()
call root.ad(this)
endif
set digit = digit + carry
set carry = digit/base
set digit = digit - digit/base*base
endloop
endmethod
method add takes integer i returns nothing
local integer base = this.base
local integer carry = 0
local thistype root = this
loop
exitwhen 0 == i
set this = next
set digit = digit + i - i/base*base + carry
set i = i/base
set carry = digit/base
set digit = digit - digit/base*base
if (head) then
set this = allocate()
call root.ad(this)
endif
endloop
call carryOver(root, carry, base)
endmethod
method addBig takes BigInt i returns nothing
local integer base = this.base
local integer carry = 0
local thistype root = this
local integer count = 0
set i = i.next
loop
exitwhen i.head
set carry = i.digit
set i = i.next
set this = next
if (head) then
set this = allocate()
call root.ad(this)
endif
set digit = digit + carry
set carry = digit/base
set digit = digit - digit/base*base
endloop
call carryOver(root, carry, base)
endmethod
method operator < takes thistype i returns boolean
loop
set this = next
set i = i.next
exitwhen head or i.head
endloop
return (head == i.head and prev.digit < i.prev.digit) or (head and not i.head)
endmethod
method eq takes thistype i returns boolean
loop
set this = next
set i = i.next
exitwhen head or i.head or digit != i.digit
endloop
return head and i.head
endmethod
method ltoe takes thistype i returns boolean
loop
set this = next
set i = i.next
exitwhen head or i.head
endloop
return (head == i.head and prev.digit <= i.prev.digit) or (head and not i.head)
endmethod
static method create takes integer i, integer base returns thistype
local thistype this = allocate()
set this.base = base
set next = this
set prev = this
set head = true
call add(i)
return this
endmethod
method clear takes nothing returns nothing
if (not next.head) then
set prev.next = thistype(0).next
set thistype(0).next = next
endif
set digit = 0
endmethod
method destroy takes nothing returns nothing
set head = false
set prev.next = thistype(0).next
set thistype(0).next = this
endmethod
method copy takes nothing returns thistype
local thistype clone = allocate()
local thistype n = clone
set clone.next = clone
set clone.prev = clone
set clone.base = base
set clone.head = true
loop
set this = next
exitwhen head
set n = allocate()
call clone.ad(n)
set n.digit = digit
endloop
return clone
endmethod
method remake takes nothing returns thistype
local thistype clone = allocate()
set clone.base = base
set clone.head = true
if (not next.head) then
set clone.next = next
set clone.prev = prev
set clone.next.prev = clone
set clone.prev.next = clone
set next = this
set prev = this
else
set clone.next = clone
set clone.prev = clone
endif
return clone
endmethod
method enq takes integer i returns nothing
local thistype n = allocate()
call ad(n)
set n.digit = i
endmethod
method push takes integer i returns nothing
local thistype n = allocate()
call adp(n)
set n.digit = i
endmethod
method toInt takes nothing returns integer
local integer i = 0
local integer base = this.base
loop
set this = prev
exitwhen head
set i = i*base+digit
endloop
return i
endmethod
method toString takes nothing returns string
local string s = ""
if (next.head) then
return "0"
endif
loop
set this = next
exitwhen head
set s = I2S(digit) + ", " + s
endloop
return s
endmethod
method subtract takes BigInt i returns nothing
local integer base = this.base
loop
set this = next
exitwhen i.head
if (digit < i.digit) then
set next.digit = next.digit - 1
set digit = digit + base
endif
set digit = digit - i.digit
set i = i.next
endloop
set base = prev
loop
set this = base
set base = prev
exitwhen 0 != digit or head
set next.prev = prev
set prev.next = next
set next = thistype(0).next
set thistype(0).next = this
endloop
endmethod
method multiply takes integer i returns nothing
local integer carry = 0
local integer base = this.base
local thistype root = this
local integer m = 0
loop
set this = next
exitwhen head and 0 == carry
if (head) then
set this = allocate()
call root.ad(this)
endif
set digit = digit*i + carry
set carry = digit/base
set digit = digit - digit/base*base
endloop
endmethod
method addString takes string s returns nothing
local integer base = this.base
local integer carry = 0
local thistype root = this
local integer i = StringLength(s)
loop
exitwhen 0 == i
set carry = S2I(SubString(s, i - 1, i))
set i = i - 1
set this = next
if (head) then
set this = allocate()
call root.ad(this)
endif
set digit = digit + carry
set carry = digit/base
set digit = digit - digit/base*base
endloop
call carryOver(root, carry, base)
endmethod
static method convertString takes string s, integer base returns thistype
local thistype this = allocate()
set this.base = base
set next = this
set prev = this
set head = true
call addString(s)
return this
endmethod
private boolean hit
private static boolean act
private method subtractFront takes BigInt i, BigInt d, integer guess returns nothing
local integer base = this.base
local thistype root = this
local boolean b
local boolean b2
local thistype mult2
local BigInt mult
local integer c = 0
loop
set this = root
set b = false
set b2 = false
set mult = d.copy()
call mult.multiply(guess)
set mult2 = mult
loop
set mult = mult.next
set mult2 = mult2.prev
exitwhen mult.head
set this = prev
set b = b or (not b2 and digit < mult2.digit)
set b2 = b2 or digit != mult2.digit
endloop
if (b) then
set guess = guess - 1
if (0 == guess) then
set this = prev
set guess = 1
exitwhen true
else
call mult.destroy()
endif
else
exitwhen true
endif
endloop
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"Solution: "+I2S(guess))
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,I2S(guess)+"*"+d.toString()+" = "+mult.toString())
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,root.toString()+" - "+mult.toString())
set mult = mult.next
loop
if (hit) then
set act = true
elseif (act) then
if (0 < c) then
call i.push(0)
endif
set c = c + 1
endif
set hit = true
if (digit < mult.digit) then
set next.digit = next.digit - 1
set digit = digit + base
endif
set digit = digit - mult.digit
set mult = mult.next
set this = next
exitwhen mult.head
endloop
set this = root
set base = prev
loop
set this = base
set base = prev
exitwhen 0 != digit or head
set next.prev = prev
set prev.next = next
set next = thistype(0).next
set thistype(0).next = this
endloop
call mult.destroy()
call i.push(guess)
endmethod
method divide takes thistype d returns integer
local BigInt r = remake()
local integer guess
local integer base = this.base
//local integer m = 90
local integer d2
set act = false
if (r.next.head and d.next.head) then
set this.next.digit = r.next.digit/d.next.digit
set r.next.digit = r.next.digit - r.next.digit/d.next.digit*d.next.digit
endif
loop
set r = r.next
exitwhen r.head
set r.hit = false
endloop
loop
exitwhen r.ltoe(d)
set guess = r.prev.digit/d.prev.digit
if (0 == guess) then
set guess = (r.prev.digit*base+r.prev.prev.digit)/d.prev.digit
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"("+I2S(r.prev.digit)+"*"+I2S(base)+" + "+I2S(r.prev.prev.digit)+")/"+I2S(d.prev.digit))
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,I2S(r.prev.digit)+","+I2S(r.prev.prev.digit)+"-> "+I2S(r.prev.digit*base+r.prev.prev.digit)+"/"+I2S(d.prev.digit))
else
set guess = (r.prev.digit*base+r.prev.prev.digit)/(d.prev.digit*base+d.prev.prev.digit)
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"("+I2S(r.prev.digit)+"*"+I2S(base)+" + "+I2S(r.prev.prev.digit)+")/("+I2S(d.prev.digit)+"*"+I2S(base)+" + "+I2S(d.prev.prev.digit)+")")
if (0 == guess) then
set guess = base - 1
endif
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,I2S((r.prev.digit*base+r.prev.prev.digit))+"/"+I2S((d.prev.digit*base+d.prev.prev.digit)))
endif
if (0 > guess) then
set guess = guess/0
endif
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"First Guess: "+I2S(guess))
call r.subtractFront(this, d, guess)
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"-> "+r.toString())
//call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"New Dividend: "+this.toString())
//set m = m - 1
//if (0 == m) then
// return r
//endif
endloop
if (act and not r.next.hit) then
call push(0)
set this = next.next
set d = allocate()
set d.next = next
set d.prev = this
set next.prev = d
set next = d
endif
return r
endmethod
endstruct
//! runtextmacro TEST()
endlibrary
Last edited:
