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)