Listen to a special audio message from Bill Roper to the Hive Workshop community (Bill is a former Vice President of Blizzard Entertainment, Producer, Designer, Musician, Voice Actor) 🔗Click here to hear his message!
The following steps are always taken. This is a more general form of long division in which no guesses are taken. It is most likely you will guess too high, but that is fine.
At later points in the algorithm, if the length of the number on the left is less than the length of 31, which is 2, then add 0 to the quotient and put another digit from the dividend into the number. This is true until there are no digits remaining in the dividend, at which point the number on the left becomes the remainder. The running time of this algorithm is O(n^2).
edit
If numerator < denominator, then answer is 0 remainder numerator. Not doing this will get you a negative remainder that's quite a bit larger than the denominator : P. You'd have to form more division in order to get the number to the correct answer.
The current BigInt isn't bugged. The older algorithm I had for the BigInt update wasn't quite right. BitInt is bugged though : ). However, I plan on making BigInt only work in powers of 2. It will allow you to output the thing to any base though. This'll allow for fast shifting. I could also do binary division, but that's going to be slower than this division because Warcraft 3 has no bitwise operators.
I'm going to try and come up with a better multiplication algorithm too : o.
I also have a pretty good modulus reduction thing going.
And thats exactly why I kept asking you for mathematical proof of this working for any input, and you kept saying your "but look, it works on this input"
Here's another algorithm. This is similar to my original, but it's quite a bit better : ). The concern is that it could get an infinite loop of +/-x from the answer. This is what happened in the original.
Code:
453893/2901 = 156r1337
Step 1: Get largest denominator digit
2
Step 2: Get largest 1-2 numerator digits greater than largest denominator digit
4
Step 3: Estimate quotient
4/2 = 2
Step 4: Multiply first digit of quotient with denominator
2*2901 = 5802
Step 5: Estimate length of quotient
len(numerator) - len(result) + 1 = len(453893) - len(5802) + 1 =
6 - 4 + 1 = 3
Step 6: Get length of quotient more digits for quotient, last being a remainder
Get remainder
4538 - 5802 = -1264
Digit #2
-12/2 = -6
Get Remainder
-6*2901 = -17406
-12649 - -17406 = 4757
Digit #3
4/2 = 2
Get remainder
2*2901 = 5802
4757 - 5802 = -1045
Normalize(3,-6,2 r-1045) -> 241r1856
Drop remainder -> 241
Step 7: Multiply guessed quotient with denominator
241*2901 = 699141
Get remainder
453893 - 699141 = -245248
Step 8: Do first estimate of -245248/2901 to determine about how off the quotient is
-2/2 = -1*
-1*2901 = -2901
6 - 4 + 1 = 3
-2452 - -2901 = 449
4/2 = 2*
2*2901 = 5802
4494 - 5802 = -1308
-13/2 = -6*
-6*2901 = -17406
-13088 - -17406 = -4318
-1,2,-6 r-4318
0,-8,-6 r-4318
-86
241 - 86 = 155
Go to step 7
155*2901 = 449655
453893 - 449655 = 4238
Do first estimate of 4238/2901
4/2 = 2
2*2901 = 5802
4 - 4 + 1 = 1
4238 - 5802 = -1564
Normalize(2, -1564) -> 1
155 + 1 = 156
Go to step 7
156*2901 = 452556
453893 - 452556 = 1337
Answer: 156r1337
Now, it could be that if there is no remainder that the +/-x will never happen, so I'm wondering if calculating the modulo first to ensure that the division doesn't f*** up is the right way to go.
Uhm, our own algorithm seems better for JASS, heh. They use a lot of bitwise operators and work with 32-bit words. We can only work with 15 bit words due to the annoying sign bit. Even then, only up to 16 bits.
So it's been a couple of days. I've been working on optimizing the algorithm.
Dividing 500 digits in the absolute worst case scenario initially took 3 full seconds. Not good. It also took 500 divisions.
The absolute worst case scenario for 500 digits now takes .33 seconds and 410 divisions. Not only does it takes slightly few divisions, but each division operation requires fewer iterations.
Is this fast enough for Warcraft 3 yet? Likely not.
Here is the inner division algorithm
QuotientCase refers to whether to append 1 to the length of divisor*quotientDigit or not. This is needed if we're going to avoid adding 0's.
After this, you divide sorta like in long division, but sloppier, N times. The N times is the length of the quotient. The N is needed because the remainder may be
larger than the divisor.
All of the Den things will give an abnormal number, that is a number that may contain digits of different signs.
Den subtraction is faster because it doesn't normalize the number. Normalized numbers are more accurate when calculating an estimated quotient, but are much more expensive. The below only calculates the leading coefficient as accurately as possible : ). The leading two might be faster, but whatever.
Calculating everything as quickly as possible gives about 800 calls to Divide. Calculating the leading alone gives about 470 calls to Divide. Calculating them all out is what, 250 or 270. This is for a 500 digit number divided by the worst case 2 digit number.
Code:
private void Divide(BigInt divisor, BigInt remainder, BigInt temp, int largeDivisor, int largeDivisor2)
{
remainder.Clear();
Swap(remainder);
QuotientCase Case = GetQuotientCase(remainder, largeDivisor, largeDivisor2);
int quotientDigit = GetQuotientDigit(remainder, largeDivisor, largeDivisor2, Case);
divisor.CopyTo(temp);
temp.MultiplySingleDigit(quotientDigit);
// the quotient will always have the following length in denormalized form
Length = remainder.Length - temp.Length + 1;
int highestDigit = Length;
this[--highestDigit] = quotientDigit;
SubtractFrontCase(remainder, temp, divisor, Case);
while (highestDigit > 0)
{
Case = GetQuotientCase(remainder, largeDivisor, largeDivisor2);
quotientDigit = GetQuotientDigit(remainder, largeDivisor, largeDivisor2, Case);
this[--highestDigit] = quotientDigit;
divisor.CopyTo(temp);
temp.MultiplySingleDigitUnsafe(quotientDigit);
SubtractFrontCaseDen(remainder, temp, divisor, Case);
}
}
Next is the main method. This comes up with an initial estimate and an initial remainder. The initial estimate should probably be as accurate as possible. After this, it will continue to estimate how far off its estimate is from the real answer until it is 0 off from the real answer ^_-. Finally it normalizes the quotient. Normalization of the quotient means both carrying all of the signs so that all of the digits have the same sign and then carrying the sign from the remainder.
Code:
public BigInt Divide(BigInt number)
{
if (Base != number.Base)
{
throw new Exception("Bases aren't equal");
}
if (number.IsZero())
{
throw new Exception("Divide by 0");
}
if (IsZero())
{
return this;
}
BigInt remainder = new BigInt(Base);
if (AbsLessThan(this, number))
{
remainder.Swap(this);
if (!SameSign(remainder, number))
{
remainder.Negate();
}
return remainder;
}
if (AbsEqual(this, number))
{
if (SameSign(this, number))
{
Clear();
Length = 1;
this[0] = 1;
}
else
{
Clear();
Length = 1;
this[0] = -1;
}
return remainder;
}
BigInt quotient = Clone();
BigInt temp = new BigInt(Base);
BigInt temp2 = new BigInt(Base);
int largeDivisor1 = number[number.Length - 1];
int largeDivisor2 = number.Length > 1 ? largeDivisor1 * number.Base + number[number.Length - 2] : Int32.MaxValue;
quotient.Divide(number, remainder, temp, largeDivisor1, largeDivisor2);
//System.Console.WriteLine("Remainder: " + remainder.ToDigits());
CalculateRemainder(this, number, quotient, remainder, temp);
remainder.Swap(temp2);
//System.Console.WriteLine("Guess: " + quotient.ToDigits());
//System.Console.WriteLine(temp2.ToDigits());
int iterations = 1;
while (temp2.AbsCompareDen(number) >= 0)
{
temp2.Divide(number, remainder, temp, largeDivisor1, largeDivisor2);
quotient.AddDen(temp2);
//System.Console.WriteLine("Guess: " + quotient.ToDigits());
CalculateRemainder(this, number, quotient, temp2, temp);
//System.Console.WriteLine($"Off By {temp2.ToDigits()}");
++iterations;
}
//System.Console.WriteLine("Off By {0}");
remainder.Swap(temp2);
quotient.Normalize();
if (!SameSign(quotient, remainder))
{
if (quotient.IsNegative())
{
quotient.AddSingleDigit(1);
remainder.Subtract(number);
}
else
{
quotient.AddSingleDigit(-1);
remainder.Add(number);
}
}
System.Console.WriteLine("Answer: " + quotient.ToDigits() + " r" + remainder.ToDigits());
Swap(quotient);
System.Console.WriteLine("\n" + iterations + " divisions");
return remainder;
}
edit
I improved the algorithm drastically by normalizing the first two digits during SubtractFrontDen : D. 470 is now down to 270 and .331 is down to .236. I just wonder how much slower JASS runs than c#.
This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
By continuing to use this site, you are consenting to our use of cookies.
you probably wanted to put the 65 into there from the previous calculation
