Extraction from long

This is a discussion on Extraction from long within the C Programming forums, part of the General Programming Boards category; I am trying to implement a version of the Karatsuba algorithm and it requires the numbers to be split up ...

  1. #1
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223

    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?
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Make sure your literals are like this:

    012937840129384012938410L

  4. #4
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398
    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.

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Quote Originally Posted by DougDbug View Post
    If you display x (i.e. cout << x ; ) ....
    You mean printf(), of course.
    Code:
    long x = 1234567890L;
    
    printf("&#37;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.

    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.

    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    > I think that would be an octal literal

    whatever, I just pounded on the keyboard.

  7. #7
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    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)
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    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]
    Last edited by dwks; 05-30-2008 at 08:28 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    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.
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  11. #11
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    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.
    I hate real numbers.

  12. #12
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  13. #13
    HelpingYouHelpUsHelpUsAll
    Join Date
    Dec 2007
    Location
    In your nightmares
    Posts
    223
    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.
    long time no C; //seige
    You miss 100% of the people you don't C;
    Code:
    if (language != LANG_C && language != LANG_CPP)
        drown(language);

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by P4R4N01D View Post
    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.)

  15. #15
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Having Buffer Problems With Overlapped I/O --
    By Sargera in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 04:46 PM
  2. Problem in Converting Unsigned long to String
    By cprogrammer_18 in forum C Programming
    Replies: 8
    Last Post: 01-14-2006, 08:57 AM
  3. Merge and Heap..which is really faster
    By silicon in forum C++ Programming
    Replies: 2
    Last Post: 05-10-2005, 05:06 PM
  4. Insertion Sort Problem
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-08-2005, 01:30 PM
  5. HUGE fps jump
    By DavidP in forum Game Programming
    Replies: 23
    Last Post: 07-01-2004, 11:36 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21