Thread: Running program until values reach ULLONG_MAX

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    5

    Running program until values reach ULLONG_MAX

    Greetings. I am writing a program that is supposed to keep trying find a palindrome by summing up number and it's reversal (123 + 321) until it either finds one, or reaches limit of unsigned long long int.
    For small numbers, it seems to be working.
    However I have been told it is not proven possible that one can find palindrome with this algorithm for number 196 yet my program finds one, witch implies an error.

    Code:
    #include <limits.h>
    const unsigned long long int a = ULLONG_MAX;
    I tried this and then checking if the numbers I am working with are still less than a, to no avail. Could you please give me a hint? Thank you!

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    You want us to give you a hint, based on one line of code?

    Code:
    $ cat foo.c
    #include<stdio.h>
    #include<string.h>
    #include<limits.h>
    void foo ( ) {
        unsigned char i = 0;
        while ( i <= UCHAR_MAX ) i++;    
    }
    
    int main()
    {
        return 0;
    }
    $ gcc -Wall -Wextra foo.c
    foo.c: In function ‘foo’:
    foo.c:6:5: warning: comparison is always true due to limited range of data type [-Wtype-limits]
    > However I have been told it is not proven possible that one can find palindrome with this algorithm for number 196 yet my program finds one, witch implies an error.
    Are you using the right printf format (for example)?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Oct 2012
    Posts
    5
    Sorry about that, but I am trying to avoid someone saying I let other people do my homework so I hoped this will be enough

    Input number:
    196
    Computed palindrome: 16623445888854432661 (iterations: 226)

    wich is a contradiction to Jason Doucette - World Records - 196 Palindrome Quest, Most Delayed Palindromic Number

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Well the generated numbers here -> Jason Doucette - 196 Palindrome Quest
    FAR FAR exceed what can be stored in an unsigned long long (on my machine, it's only just 20 decimal digits)

    You just stumbled into an answer through ignoring numeric overflow.

    This program has continued the above sequence to 32,000,000 iterations. This resulted in a number over 13,000,000 digits long, which has yet to produce a palindrome. It took just over 283 days of calculations on a 266 MHz and a 400 MHz desktop machine, running at separate times.
    You need to implement some kind of bignum library (like GMP).

    Not to mention a hell of a lot of CPU power, and a lot of patience.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Run this program (or add the according printf()-call inside your loop) and you will notice that after the 40th iteration you have an overflow and all following calculations are wrong:
    Code:
    #include <stdio.h>
    
    unsigned long long palindrome(unsigned long long n);
    
    int main(void)
    {
        int i;
        unsigned long long number = 196;
    
        for (i = 0; i < 50; i++)
        {
            printf("%3d %22llu\n", i, number);
            number += palindrome(number);
        }
        return 0;
    }
    
    unsigned long long palindrome(unsigned long long n)
    {
        unsigned long long p = 0;
        while (n > 0)
        {
            p *= 10;
            p += n % 10;
            n /= 10;
        }
        return p;
    }
    Bye, Andreas

  6. #6
    Registered User
    Join Date
    Oct 2012
    Posts
    5
    Well thank you for trying to help but I want the program to stop the moment it reaches limit of unsigned long long int and say 'Couldn't find the palindrome.'; my
    Code:
    if ((number >= ULLONG_MAX)||(reversed >= ULLONG_MAX)) {printf("Couldn't find the palindrome..\n"); return(1);}
    does not work.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > if ((number >= ULLONG_MAX)||(reversed >= ULLONG_MAX))
    Think about this.

    Say MAX is 10.
    and you want to detect whether 6+5 overflows.
    Doing 6+5 does no good, since it wraps around and you end up comparing 1 with 10.

    So instead of
    if ( 6 + 5 >= 10 )
    you need to write
    if ( 6 >= 10 - 5 )
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    If the sum of two unsigned integers is less than one or both of the original numbers, the result overflowed.

    It other words: c = a + b overflows using unsigned integers of the same type, if and only if (c < a) || (c < b).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 15
    Last Post: 06-19-2012, 02:58 PM
  2. ULLONG_MAX Question
    By DSM in forum C++ Programming
    Replies: 5
    Last Post: 04-01-2010, 01:13 PM
  3. Problem with ULLONG_MAX
    By vincent01910 in forum C Programming
    Replies: 11
    Last Post: 05-05-2009, 06:39 AM
  4. How can I reach Protected Variables?
    By zayzay in forum C++ Programming
    Replies: 8
    Last Post: 07-14-2005, 06:32 AM
  5. how to reach MySQL??
    By mergoktas in forum C Programming
    Replies: 2
    Last Post: 09-28-2003, 10:36 AM