Extraction from long

I am trying to implement a version of the Karatsuba algorithm and it requires the numbers to be split up into x1,x2,y1,y2. The problem is dividing 7890123456789012 by say 10000, results in -204890. Not too sure but I don't think the division '/' operator can handle large numbers. E.g. x = 7890123456789012, how would I extract the low order 8 digits and the rest and separate it into two variables. Bit shifting? There should be some reasonably quick way of ding it. Or am I completely missing the obvious?

Look in limits.h to see what LONG_MAX is for your system. It's only guaranteed to be ten digits long, so your sixteen-digit number may not fit. You should be able to use long long instead.

Make sure your literals are like this:

012937840129384012938410L

Right. It's not the division operator. I suspect that "x" does not really hold that value. If you display x (i.e. cout << x ; ) I suspect you will not see 7890123456789012.

Quote:

---

Originally Posted by DougDbug

If you display x (i.e. cout << x ; ) ....

---

You mean printf(), of course. :)

Code:

---

long x = 1234567890L;

printf("%ld\n", x);

---

(This is the C forum.)

Code:

---

012937840129384012938410L

---

I think that would be an octal literal, because it starts with a zero. A long octal literal, mind you. Still, that's probably not what the OP wanted.

Quote:

---

Look in limits.h to see what LONG_MAX is for your system. It's only guaranteed to be ten digits long, so your sixteen-digit number may not fit.

---

Well, it's actually only guaranteed to be 2^31-1, which is nine digits plus one digit that can only be a 0, 1, or 2. :)

Quote:

---

You should be able to use long long instead.

---

long long is C99 specific. You're probably right that it could be used, but the OP should at least be aware that it is C99.

> I think that would be an octal literal

whatever, I just pounded on the keyboard. :p

Longs don't seem to be working well, I have this which should return an unsigned value:

Code:

---

unsigned long long shift(unsigned long long a) {
        return a / 10000;
}
printf("7890123456789012 : %ld\n", shift(7890123456789012LL));
---Outputs:---
7890123456789012 : -1261636786

---

I compiled this using Dev-C++. It still does not explain how to break up the number into parts without hard-coding x1 and x2 e.g.:
x = 7890123456789012
x1 = 78901234 (the first 8 digits of x)
x2 = 56789012 (the last 8 digits of x)

Of course, to print an unsigned long long, you would have to use %llu, and not %ld.

Or at least that's what the standard says; what MinGW says is this.

Note that you need to use &#37;lld to print a long long, or %llu to print an unsigned long long. However, Dev-C++'s implementation of printf() does not support printing long longs, so you're pretty much out of luck there.

[edit] Is this sort of what you're looking for?

Code:

---

$ cat parts.c
#include <stdio.h>

int main() {
    int number = 11112222;
    printf("%i\n", number / 10000);
    printf("%i\n", number % 10000);
    return 0;
}
$ ./parts
1111
2222
$

---

[/edit]

Yes that was what I was looking for. It makes it hard to operate on extremely large numbers when the compiler can't print them.

I suggest you not to work in decimal representation for performance issue. Since you want to implement Karatsuba, I guess it's because you want something faster than the normal long multiplication algorithm, but if you are using division and modulo operator, you are quite losing the benefits you could win from it. I suggest you to work in hexadecimal, which is a convenient base for you and for your computer. Now, when you want to split your number, you just have to use the AND and the right shift operator. Taking the same example as DWKS, it would looks something like this:

Code:

---

#include <stdio.h>

int main() {
    int number = 0x11112222;
    printf("%X\n", number >> 16);
    printf("%X\n", number & 0xFFFF);
    return 0;
}

---

Also, when computing the final result using Karatsuba, you has to multiply some value you pre-calculated. If you don't work in hexadecimal or something similar, you'll basically have to use the multiply operator instead of the left shift operator and you'll basically end with something slower than a well implemented long multiplication algorithm.

Note that I never implemented Karatsuba algorithm so there's might be people with more knowledge about it on the board.

By the way, he's one way you can print an unsigned long long without having to use a debugger.

Code:

---

#include <stdio.h>
#include <limits.h>

void print_ull(unsigned long long n);

int main() {
    print_ull(1234567890123456789ULL);
   
    return 0;
}

void print_ull(unsigned long long n) {
    unsigned long long x;
   
    for(x = 1; x < n; x *= 10);
   
    for(;;) {
        x /= 10;
        if(!x) break;
       
        putchar((int)(n / x &#37; 10) + '0');
    }
   
    printf("\n");
}

---

It's probably a really bad way to do it. It's just something I wrote briefly just now, but maybe it will be helpful.

Thanks for the suggestion of using hex, and a much quicker way to split each long number. Also, I should be able to use printing a ull without a debugger (esp. since I don't have a debugger). This is what I have now, the multiply function uses bit shifts created from psudeocode on wiki, wild guess that a working algorithm is much more complicated than this:

Code:

---

long karatsubaAlg(int x, int y) {
       
        int x1 = x >> 16;
        int x2 = x & 0xFFFF;
        int y1 = y >> 16;
        int y2 = y & 0xFFFF;
        long a, b, c, k;
        a = multiply(x1, y1);
        b = multiply(x2, y2);
        c = multiply(x1+x2, y1+y2);
        k = c - a - b;
        return multiply(a, 100 + multiply(k, 10)+b);
}

---

This does not produce the correct result, e.g.

Code:

---

0x11112222L * 0x1111EAL = 17217014364469104 //MS Calc gives: 12355012F7514

---

I read an article on wikipedia - the place that explains a hell of alot, not very well - and find it annoying that there is a lack of sites that explain it using terms "normal people" can understand. I only just discovered bit shifts yesterday and am used to biting off more than I can chew (it worked with windows programming :)). I was thinking of implementing other algorithms like this one but they will all be ridiculously hard to understand - they were probably written by the same people who wrote the maths pages on wiki :) ha.

Quote:

---

Originally Posted by P4R4N01D

Code:

---

long karatsubaAlg(int x, int y) {
       
        int x1 = x >> 16;
        int x2 = x & 0xFFFF;
        int y1 = y >> 16;
        int y2 = y & 0xFFFF;
        long a, b, c, k;
        a = multiply(x1, y1);
        b = multiply(x2, y2);
        c = multiply(x1+x2, y1+y2);
        k = c - a - b;
        return multiply(a, 100 + multiply(k, 10)+b);
}

---

---

One must wonder why you turned the answer (I'm assuming according to the same wikipedia page that you read) of 2^32 * a + b + 2^16 * k into the line in red above. (And of course the multiplications by powers of 2 are bitshifts by 32 and 16, respectively.)

I'm not familiar with this Karatsuba algorithm, but perhaps you want to use something like this?

Code:

---

        int x1 = x >> 16;
        int x2 = (x & 0xFFFF) >> 16;

---

and so on for y2?

You might want to look at this, it seems fairly legible. http://everything2.com/title/Karatsu...multiplication

Here are some implementations of Karatsuba multiplication, but they're not very legible.

• http://ozark.hendrix.edu/~burch/proj/karat/karat.txt (in C)
• http://www.cs.princeton.edu/introcs/...suba.java.html (in Java)

I can't find that line where I originally got that return, anyway I changed it and now the same operation returns 17217012081137461, slightly closer:

Code:

---

return ((a << 32) + b + (k << 16));

---

The suggestion of dwks gives a larger value: 17217012061250081 and printing x2 comes out as 0. Thanks for the links, though.

The algorithm you have gives the right answer, on the assumption that multiply does the right thing:
a = 0x12221
b = 0x2637514
c = 0x3989601
k = 0x133fecc
Adding:

Code:

---

1222100000000
      2637514
  133fecc0000
-------------
12355012f7514

---

Check that a and b and c and k are getting calculated correctly.

Oh, I get a different answer:

Code:

---

printf("Multiply %X * %X * %X = %X", 0x12221, 0x2637514, 0x3989601, multiply(multiply(0x12221, 0x2637514), 0x3989601));
---
Multiply 12221 * 2637514 * 3989601 = B1937794

---

Here is the multiply function, I know it works for small ints:

Code:

---

long long multiply(long multiplier, long multiplicand) {
        long product = 0;
        while (multiplicand) {
                if (multiplicand & 1) product = product + multiplier;
            multiplier = (long)(multiplier << 1);
            multiplicand = (long)(multiplicand >> 1);
        }
        return product;
}

---

Quote:

---

Originally Posted by P4R4N01D

Oh, I get a different answer:

Code:

---

printf("Multiply %X * %X * %X = %X", 0x12221, 0x2637514, 0x3989601, multiply(multiply(0x12221, 0x2637514), 0x3989601));
---
Multiply 12221 * 2637514 * 3989601 = B1937794

---

Here is the multiply function, I know it works for small ints:

Code:

---

long long multiply(long long multiplier, long long multiplicand) {
        long long product = 0;
        while (multiplicand) {
                if (multiplicand & 1) product = product + multiplier;
            multiplier = (long long)(multiplier << 1);
            multiplicand = (long long)(multiplicand >> 1);
            /* These casts shouldn't be necessary anyway; do multiplier <<= 1; and multiplicand >>= 1; instead */
        }
        return product;
}

---

---

And that wasn't quite what I meant -- you need to check that a really is 0x12221, b really is 0x2635714, and that k really is 0x133fecc. If so, then your shifts will do the right thing.

I managed to get the debugger working :). a and b come out correct, but k does not. This is not suprising as k is the output of the function and a and b are inputs. Here is the input to both the functions:

Code:

---

multiplier = 74273, multiplicand = 40072468
multiplier = -109920364, multiplicand = 60331521

---

The first number is 0x12221, correct. 2nd: 2637514 Correct. 3rd negative so incorrect. 4th: 3989601 correct. Changing the function to your suggestion I get on the 2nd call:

Code:

---

multiplier=17236597112045569, multiplicand=181012359443712784

---

But if you get a and b and c right (the 12221, the 2637514, and the 3989601) right, k is just c - a - b. There's no multiplying involved.

I checked again: a, b and c come out and k didn't seem to at first, but sure enough they come out correct (I lost a):
b= 40072468, c=60331521 and k = 20184780. The only thing it could possibly now is the return statement where (after execution):
a=74273, k = 19961653. I compared them to ms calc, accurate for simple operations not involving (). The whole operation returns: 60108394 (when the return statement is done using calc), which trying to do it using calc returns: 320322975790356. The function prints: 172109939549968181. Hope I didn't make a mistake!

It's the second time someone say this in this thread but i repeat that if you want to print long or long long value, you has to put a length specifier:

Code:

---

printf("Multiply %X * %X * %X = %X", 0x12221, 0x2637514, 0x3989601, multiply(multiply(0x12221, 0x2637514), 0x3989601));

---

cecomes

Code:

---

printf("Multiply %llX * %llX * %llX = %llX", 0x12221, 0x2637514, 0x3989601, multiply(multiply(0x12221, 0x2637514), 0x3989601));
---
Multiply 12221 * 2637514 * 3989601 = B1937794

---

I didn't read compltely the last posts (it's morning, heh) but I still might be an issue...

And then Dev-C++'s printf doesn't print long longs properly, so I guess you'd have to use my function and convert it to hex, write a function which does it for you, or use a debugger. :)