Sign in to follow this  
xytor

Simple division is too slow

Recommended Posts

Hi, I am implementing my own division algorithm for a large real number library. Although speed is not an issue, there is one case in which it is extremely slow.

The core part of the algorithm finds the integer part and a proper fraction. It works by promoting both numbers to (sometimes much larger) integers and using repeated subtraction.

This algorithm is 100% correct in all my test cases, but for a certain type of test case is extremely slow:
If the dividend is much larger than the divisor.

For example, 200.0 / 0.001 gets converted to 200000 / 1.
Then, it takes 200000 repeated subtractions to get 200000 + 0/1.

Now, this is just a silly example but it shows that a large dividend and a small divisor produce a very slow result.

Is there any way to optimize my algorithm to handle this case faster?

Thanks!

Share this post


Link to post
Share on other sites
Binary long division will be faster than your current method, but since we already have a full set of arithmetic operations for 32 bit integers, we can do faster if we work with full 32 bit integers as digits (ie in base 2^32).

Share this post


Link to post
Share on other sites
I suppose I could, but both of those methods require a cumbersome base change from base 10.
I'm looking for an optimization to my algorithm, not an entire new one. Is that possible?

Share this post


Link to post
Share on other sites
Optimizing an implementation of an algorithm, without changing the logic behind it, usually means optimizing the individual steps (ie. your subtraction step). In your case, the problem most likely isn't the time it takes to do one such step though, but rather the shear number of steps required. So the only way to really get better performance is to rewrite it so that there are less steps required, which means you're going to have to change your algorithm.

But anyway, you say it requires a base change. Does this mean you are currently working in base 10? If so, then you can also use base 10 long division.

Share this post


Link to post
Share on other sites
Actually, I think I figured out an optimization, and it seems to work:

Old algorithm:
Keep subtracting the divisor from the dividend until it reaches zero (or less)
The number of subtractions is the integer part of the division.

New algorithm:
Let X be (digits in dividend - digits in divisor) if that difference is at least 2, otherwise X is 1.
Keep subtracting the divisor*X from the dividend until it reaches zero (or less)
The (number of subtractions)*X is the integer part of the division.

However, this is not much of an improvement and the time still scales very quickly when the dividend gets larger than the divisor.

But I was hoping to flesh out this idea of taking care of as many subtractions as possible in one go by using multiplication. However, when I went too high (setting X to 10^(digits in dividend - digits in divisor)) it caused some calculations to be wrong.

Share this post


Link to post
Share on other sites
Quote:
Original post by xytor
I suppose I could, but both of those methods require a cumbersome base change from base 10.
I'm looking for an optimization to my algorithm, not an entire new one. Is that possible?

Wait are you not storing your huge numbers in a bit format?

Nah you want an entirely new one. Your method is extremely naive and expensive.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
You learned a much faster division algorithm in elementary school. Try using that.


Repeated subtraction is the only way that I can see to do it.
Long division sounds like a great idea when we have the multiplication table memorized. But what about something like 1/245205982340? Long division seems to become impossible with a large divisor.

Share this post


Link to post
Share on other sites
Ah! I've figured out a way using long division and trial multiplication:


Let "partial dividend" be the first digit in dividend.
For each digit "i" in dividend:
For each number "j" 9 to 0:
if divisor*j is less than or equal to the partial dividend:
add j as the next digit of the answer.
break out of loop

new partial dividend is:
(( partial dividend - (answer's newest digit * divisor) ) * 10) + ("i+1"th digit of dividend)



Share this post


Link to post
Share on other sites
Quote:
Original post by xytor
Quote:
Original post by alvaro
You learned a much faster division algorithm in elementary school. Try using that.


Repeated subtraction is the only way that I can see to do it.
Long division sounds like a great idea when we have the multiplication table memorized. But what about something like 1/245205982340? Long division seems to become impossible with a large divisor.


Well, it's not impossible, although it is tricky. If you are using base 10 to represent your numbers, you could use a table with the divisor multiplied by 0, 1, 2, 3, ..., 9 and find at each step what is the largest of those that is less or equal than your accumulator (I really don't know the name for it, but if you try to do long division by hand you'll understand). If you use base 2 instead, you only need to know if the next digit is going to be a 0 or a 1, and that's trivial. So perhaps you should start there (as Sirisian suggested).

It can be made to work in any base, and the fastest results would probably be using base 2^32 or 2^64, but any long-division algorithm will be polynomial on the length of the operands, while your current algorithm is exponential.

Share this post


Link to post
Share on other sites
Yes, we seemed to post at the same time :)
My old repeated subtraction was indeed highly exponential, but my long division with trial multiplication algorithm from the last post seems to be linear with the number of digits in the operands.

Share this post


Link to post
Share on other sites
Quote:
Original post by xytor
Yes, we seemed to post at the same time :)
My old repeated subtraction was indeed highly exponential, but my long division with trial multiplication algorithm from the last post seems to be linear with the number of digits in the operands.


Well, the number of steps is linear, but each step requires making a multiplication of the divisor times a digit, which takes time linear in the length of the divisor, and a similar-size subtraction. I believe the algorithm then takes something like O(n*m), where n is the length of the dividend and m is the length of the divisor.

Share this post


Link to post
Share on other sites
That's good enough for now. I've been wondering about the bit method. Is this usually done where these bits tightly packed or does each unsigned char hold 2 or 3 "decimal digits" worth of information, depending on if it can?

For example: 123456789 could be held in an array of 4 uchars like this:
123 45 67 89
(base 10 is being used for easy reading)

Alternatively, we could tightly pack the bits into 4 uchars with 123456789's binary representation:
7 91 205 21

The first way is easy to encode and decode, but I'm not sure if the math will work. I can't figure out how to encode/decode using the second way at all.

Share this post


Link to post
Share on other sites
You'd just store the number in binary. Like in your second way.

As you know decimals are base 10. So given the number 1200 you can write it like:
1 * 10^3 + 2 * 10^2 + 0 * 10^1 + 0 * 10^0
aka:
1 * 10^3 + 2 * 10^2 = 1200

Each coefficient can be between 0 and 9 inclusive.

In binary you'd represent it like:
1 * 2^10 + 1 * 2^7 + 1 * 2^5 + 1 * 2^4 = 1200

where each coefficient can be 0 or 1.

There has to be a well documented way of going from a string representing an integer to a binary number in bits. Every string to integer function in the world does it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sirisian
There has to be a well documented way of going from a string representing an integer to a binary number in bits. Every string to integer function in the world does it.


Well, I could write a string to integer function too, it's easy because a single integer isn't fragmented and I can simply do my first method, starting from the least significant digit.
The problem is that I need to handle extremely large numbers, so I need to use and array of uchars. That first method ceases to be viable as-is because I somehow need to squish the leading zero's of each uchar in the array and pack real data in their place.
Then, the problem becomes decoding this binary soup. Not to mention doing math with it.

Share this post


Link to post
Share on other sites
As I mentioned at earlier in this thread, using base 2^32 or 2^64 is probably the fastest, but it's tricky. This means using unsigned 32-bit or 64-bit integers as your "digits". This is what GMP does.

Since the product of two 1-digit numbers is a 2-digit number, you need to have a way of multiplying two 32-bit integers that yields a 64-bit integer (similarly, a 128-bit result for multiplying two 64-bit integers). Processors do provide such an instruction, and you may need a bit of assembly to access it.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Since the product of two 1-digit numbers is a 2-digit number, you need to have a way of multiplying two 32-bit integers that yields a 64-bit integer (similarly, a 128-bit result for multiplying two 64-bit integers). Processors do provide such an instruction, and you may need a bit of assembly to access it.


Couldn't I do it in base 2^16, and use 32-bit uint for it? Then, if there is a multiplication, I check if the result is bigger than 2^16. If it is, I subtract off 2^16, put it in a new adjacent uint.

Speaking of which, with all this array resizing, I think I'll use std::vector instead of pure dynamic arrays. The algorithm complexity stays the same and the overhead is acceptable.

Share this post


Link to post
Share on other sites
This is slightly off-topic, but is there a way of linking-up multiple 32-bit word divisions (or more precisely 64-by-32 division) to perform multi-word division, as opposed to resorting to the traditional binary method? I've tried my hand at doing this once or twice over the years and it seems like it ought to be possible, for symmetry with multiplication if nothing else.

The case of a multi-word dividend and a single-word divisor is straightforward at least, but beyond that I'm thoroughly stumped.
uint32_t divide(uint32_t *numer /* big-endian */, uint32_t denom, size_t len) {
uint64_t acc = 0;
while(len--) {
acc = acc << 32 | *numer;
*numer++ = acc / denom;
acc %= denom;
}
return acc;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
I don't understand why that code would work. The multiplication by 10 seems completely wrong.


It was completely wrong, and so I deleted the post. Perhaps the numbers were not in base 2^16 after all.

Here is my program playing around with both encoding and adding of these numbers. It's completely wrong, but I think my main problem might be with the encoding method.


#include <iostream>
#include <vector>
using namespace std;

typedef unsigned int digit;
#define DIGIT_MAX 65535

std::ostream& operator<< (std::ostream& out, std::vector<digit> v)
{
int numV = int(v.size()) - 1;
for(int i=numV;i>=0;--i)
{
out<<v[i]<<" ";
}
return out;
}

int main()
{
std::vector<digit> numbers;
std::vector<digit> numbers2,numbers3;

char* str = "11223344556677889900";
int strLen = (int)strlen(str);
unsigned int multiplier;
//encoding
for(int i=strLen-1;i>=0;--i)
{
if(numbers.empty() || (numbers.back() + (str[i] - '0') * multiplier) > DIGIT_MAX)
{
numbers.push_back(0);
multiplier = 1;
}
numbers.back() = numbers.back() + (str[i] - '0') * multiplier;
multiplier *= 10;
}
numbers2 = numbers;
std::cout<<numbers<<std::endl;
std::cout<<numbers2<<std::endl;
//adding (completely wrong)
digit carry = 0;
for(size_t i=0;i<numbers.size();i++)
{
digit sum = numbers[i] + numbers2[i];
if(carry)
{
if(sum<DIGIT_MAX+1)
sum = sum*10 + carry;
else
sum = sum + carry;
}
carry = sum / (DIGIT_MAX+1);
numbers3.push_back(sum % (DIGIT_MAX+1));
}
numbers3.push_back(carry);
std::cout<<numbers3<<std::endl;
}




Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this