String of digits, certain radix, perform division

[Tomás Ó hÉilidhe]

I have a radix, and I have a string of digits representing a number:

unsigned digits[] = {1,5,12,7,9,10,4,8};

The radix is 13. The most significant digit is on the left. So the
actual value of this number is calculable as:

1*(13^0) + 5*(13^1) + 12*(13^2) + 7*(13^3) + 9*(13^4) + 10*(13^5) +
4*(13^6) + 8(13^7)

I'm stuck with this format, I can't change it. As parameters to my
function, I get the radix, the digit array, and a pointer to the last
digit. So altogether its:

struct Number {
unsigned radix;
unsigned *p_flast_digit;
unsigned digits[N];
};

OK now so what I want to do is divide this number by a particular
divisor. The divisor is held in a normal integer type (not as a string
of digits). Of course in order to perform this calculation, I could
simply use the expression I show above to convert the digit string to
a fully-fledge integer type, but I can't do that because the number is
*ridiculously* big, bigger than can be stored in a 64-Bit number.

So I got out a pen and paper and thought about ways of achieving this.
I ended up writing out a long-division sum by hand and then analysing
the steps I made to calculate it. I then started coding my method.

So basically it works as follows:

* I have a pointer to the most significant digit (which is at the end
of the string of digits). Let's call this pointer simply "p".
* I have an integer variable that holds a "sum of digits", and it
starts off as zero. What happens is I add "*p" to the sum_of_digits,
and then I decrement "p". I keep doing this in a loop until
sum_of_digits becomes greater than or equal to divisor, so the loop
would be:

unsigned sum_of_digits = 0;

for (;
{
sum_of_digits += *p;

if (sum_of_digits >= divisor) break;

--p;
}

(Of course I need to make allowances for running out of digits but
bear with me)

* When sum_of_digits becomes greater than or equal to the divisor, I
perform a division (i.e. sum_of_digits / divisor).
* I take the result of this division and I use it as the most
significant digit of the result. Then I take the remainder and I
prefix it to the original number replacing the digits I've just
divided into (exactly how you'd do it with a pen and paper). Then I
start again, dividing the divisor into this new number, taking down
extra digits as I need them. The result I get from the second division
is used as the second most significant digit of the result. Perform
another division, I get the third most significant digit, and so on.

Is my pen-and-paper approach a bit ridiculous, or is it a good way of
going about this?

 

[Coos Haak]

Op Sat, 25 Oct 2008 01:11:28 -0700 (PDT) schreef Tomás Ó hÉilidhe:

I have a radix, and I have a string of digits representing a number:

unsigned digits[] = {1,5,12,7,9,10,4,8};

The radix is 13. The most significant digit is on the left. So the
actual value of this number is calculable as:

1*(13^0) + 5*(13^1) + 12*(13^2) + 7*(13^3) + 9*(13^4) + 10*(13^5) +
4*(13^6) + 8(13^7)

That formula is when the most significant digit is on the right.
Try
1*(13^7) + 5*(13^6) + 12*(13^5) + 7*(13^4) + 9*(13^3) + 10*(13^2) +
4*(13^1) + 8(13^0)

And don't forget that in C, ^ is no exponentiation.

 

[CBFalconer]

I have a radix, and I have a string of digits representing a
number:

unsigned digits[] = {1,5,12,7,9,10,4,8};

The radix is 13. The most significant digit is on the left. So
the actual value of this number is calculable as:

1*(13^0) + 5*(13^1) + 12*(13^2) + 7*(13^3) + 9*(13^4) + 10*(13^5)
+ 4*(13^6) + 8(13^7)

Where, again, is the most significant digit? You said "left," but
the formula indicates "right."

I'm stuck with this format, I can't change it. As parameters to
my function, I get the radix, the digit array, and a pointer to
the last digit. So altogether its:

.... snip ...

It doesn't match any notion of "division" I've run into, because
you've forgotten something fairly important. Hint: Your example
number uses the radix 13. If the radix were instead given as 42,
how would that affect your sum of digits?

Is the approach a "good way?" It depends on what you mean by
"good." I'd suggest you look into TAOCP volume II "Seminumerical
Algorithms."

He's not dividing, he is evaluating the number.

He's got the information he needs, except the value of the radix.
The difference between the two pointers gives the order of the
polynomial. He needs to start with the most significant, not the
least significant, digit. I.e. calculate:

((((((((8)*13) + 4)*13 + 10)*13 + 9)*13 + 7)*13 + 12)*13 + 5)*13
+1)

For generality, replace 13 by the value of radix. When the
accessing pointer gets reduced to the 0th level pointer, the
algorithm is done. Note the absence of exponentiation.

long int eval(p, p1, radix) {
long int value = 0;

while (p1 != p) {
value = value * radix + *p1;
p1--;
}
return value;
} /* eval */

 

[Ben Bacarisse]

I have a radix, and I have a string of digits representing a
number:

unsigned digits[] = {1,5,12,7,9,10,4,8};

The radix is 13. The most significant digit is on the left. So
the actual value of this number is calculable as:

1*(13^0) + 5*(13^1) + 12*(13^2) + 7*(13^3) + 9*(13^4) + 10*(13^5)
+ 4*(13^6) + 8(13^7)

Where, again, is the most significant digit? You said "left," but
the formula indicates "right."

I'm stuck with this format, I can't change it. As parameters to
my function, I get the radix, the digit array, and a pointer to
the last digit. So altogether its:

... snip ...

It doesn't match any notion of "division" I've run into, because
you've forgotten something fairly important. Hint: Your example
number uses the radix 13. If the radix were instead given as 42,
how would that affect your sum of digits?

Is the approach a "good way?" It depends on what you mean by
"good." I'd suggest you look into TAOCP volume II "Seminumerical
Algorithms."

He's not dividing, he is evaluating the number.

What did you think the OP meant by:

| OK now so what I want to do is divide this number by a particular
| divisor. The divisor is held in a normal integer type (not as a string
| of digits).
|...
| I ended up writing out a long-division sum by hand and then analysing
| the steps I made to calculate it. I then started coding my method.

followed by the algorithm that Eric was commenting on?

He's got the information he needs, except the value of the radix.
The difference between the two pointers gives the order of the
polynomial. He needs to start with the most significant, not the
least significant, digit. I.e. calculate:

((((((((8)*13) + 4)*13 + 10)*13 + 9)*13 + 7)*13 + 12)*13 + 5)*13
+1)

For generality, replace 13 by the value of radix. When the
accessing pointer gets reduced to the 0th level pointer, the
algorithm is done. Note the absence of exponentiation.

long int eval(p, p1, radix) {
long int value = 0;

while (p1 != p) {
value = value * radix + *p1;
p1--;
}
return value;
} /* eval */

Even if p, p1 and radix are given a type this looks wrong (p must
point before the least significant element of array). Fix this and
you hit the OP's statement that the number is known not to fit in any
integer type available to him.

 

[Nick Keighley]

Tomás Ó hÉilidhe wrote:

I have a radix, and I have a string of digits representing a number:

unsigned digits[] = {1,5,12,7,9,10,4,8};

The radix is 13. The most significant digit is on the left. So the
actual value of this number is calculable as:

1*(13^0) + 5*(13^1) + 12*(13^2) + 7*(13^3) + 9*(13^4) + 10*(13^5) +
4*(13^6) + 8(13^7)

     Where, again, is the most significant digit?  You said
"left," but the formula indicates "right."

I'm stuck with this format, I can't change it. As parameters to my
function, I get the radix, the digit array, and a pointer to the last
digit. So altogether its:

struct Number {
    unsigned radix;
    unsigned *p_flast_digit;
    unsigned digits[N];
};

     You also need the number of digits, or equivalent information.
Is that `N'?  If so, what's the use of the pointer?

since the pointer indicates the "last" digit. It indicates how
many digits there are. I'm guessing that N is just some large number

<snip>

 

[Thad Smith]

I have a radix, and I have a string of digits representing a number:

unsigned digits[] = {1,5,12,7,9,10,4,8};

The radix is 13. The most significant digit is on the left. So the
actual value of this number is calculable as:

1*(13^0) + 5*(13^1) + 12*(13^2) + 7*(13^3) + 9*(13^4) + 10*(13^5) +
4*(13^6) + 8(13^7)

As others mentioned, this is inconsistent.

OK now so what I want to do is divide this number by a particular
divisor. The divisor is held in a normal integer type (not as a string
of digits). Of course in order to perform this calculation, I could
simply use the expression I show above to convert the digit string to
a fully-fledge integer type, but I can't do that because the number is
*ridiculously* big, bigger than can be stored in a 64-Bit number.

So I got out a pen and paper and thought about ways of achieving this.
I ended up writing out a long-division sum by hand and then analysing
the steps I made to calculate it. I then started coding my method.

That is a valid approach. It works well if the maximum divisor times
(radix+1) can be represented as a simple integer type.

So basically it works as follows:

* I have a pointer to the most significant digit (which is at the end
of the string of digits). Let's call this pointer simply "p".
* I have an integer variable that holds a "sum of digits", and it
starts off as zero. What happens is I add "*p" to the sum_of_digits,
and then I decrement "p". I keep doing this in a loop until
sum_of_digits becomes greater than or equal to divisor, so the loop
would be:

unsigned sum_of_digits = 0;

for (;
{
sum_of_digits += *p;

if (sum_of_digits >= divisor) break;

--p;
}

You probably realize by now that instead of simply summing, you want to
convert a series of digits to their binary value, so each time multiply the
prior value by the radix, then add the new digit. Now that you have a
binary value, divide by the divisor, generating a quotient digit. Save the
digit. Multiply the remainder by the radix, then add the divident digit, etc.