Thread: anything that can handle a 1000 digit number

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    808

    anything that can handle a 1000 digit number

    The problem is to work out the first Fibonacci number that is 1000 digits long. I have calculated all the numbers up to f1000 = f999+f998 using a spreadsheet but there doesn't seem to be a pattern. Sometimes it takes 5 goes to get another digit in the answer sometimes it takes 4.

    It seemed there was a pattern emerging as in it would take 3 5's and then a 4 (19 turns for example f21 - f40 would be an increase of 4 digits 5 , 5, 5, 4) then 2 lots of 4 5's then a 4 followed by another 4 5's then a 4. However f308 to f337 took 5 5's then a 4 ie 29 moves and f337 to 351took only 2 5's then a 4 (14 turns)

    it also doesn't follow the pattern of 19 followed by 2 24's at f174 to f217 ( 19 24 19 instead of 19 24 24) it does this again at f619 - f682.

    all this to say am i thrashing around on a wild goose chase and there is a type that will handle numbers of that size or something i can use with strings instead

  2. #2
    Registered User
    Join Date
    Feb 2019
    Posts
    1,077
    Use libgmp if you want to deal with big numbers...

    And, since:
    anything that can handle a 1000 digit number-fib1-png
    It's easy to demonstrate that a nth Fibonaacci number N(n) algarisms given by:
    anything that can handle a 1000 digit number-fib2-png
    PS: The previous equation to N() was wrong.
    Attached Images Attached Images anything that can handle a 1000 digit number-fib2-png 
    Last edited by flp1969; 05-29-2023 at 08:17 AM.

  3. #3
    Registered User
    Join Date
    Dec 2017
    Posts
    1,652
    Project Euler problems are not so much programming problems as math problems (Euler being a famous mathematician and towel-wearer).

    flp's formula doesn't look right.
    Here's a couple of formulas that work:
    Code:
        printf("%.0f\n", ceil(((n - 1) * log(10) + log(5) / 2) / log(phi)));
        printf("%.0f\n", ceil((n + log10(5) / 2 - 1) / log10(phi)));
    A simplistic way of doing it (pretty mindless and I don't think it's 100% foolproof although it gets the same answer as the formulas up to at least n=10000000):
    Code:
    #include <stdio.h>
     
    typedef unsigned long ul;
     
    int main() {
        ul a = 0, b = 1;
        int i = 0;
        for (int cnt = 0; ; ++i) {
            int cnt2 = 1;
            for (ul x = a; x >= 10; x /= 10) ++cnt2;
            if (cnt + cnt2 >= 1000) break;
            ul c = a + b; a = b; b = c;
            for ( ; a > 1000000000000000lu; a /= 10, b /= 10) ++cnt;
        }
        printf("%d\n", i);
        return 0;
    }
    And that's the world in a nutshell, an appropriate receptacle.

  4. #4
    Registered User
    Join Date
    Feb 2019
    Posts
    1,077
    Yep... john.c is right. Actualy, the equation to calculate the number of decimal algarisms from F(n) is:

    anything that can handle a 1000 digit number-n-png

    Take a look:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <gmp.h>
    #include <math.h>
    
    mpz_t *fib ( unsigned int n, mpz_t *result )
    {
      mpz_t fibseq[3];
    
      mpz_inits ( fibseq[0], fibseq[1], fibseq[2], NULL );
    
      mpz_set_si ( fibseq[0], 0 );
      mpz_set_si ( fibseq[1], 1 );
    
      for ( ; n >= 2; --n )
      {
        mpz_add ( fibseq[2], fibseq[0], fibseq[1] );
        mpz_set ( fibseq[0], fibseq[1] );
        mpz_set ( fibseq[1], fibseq[2] );
      }
    
      mpz_set ( *result, fibseq[n] );
    
      mpz_clears( fibseq[0], fibseq[1], fibseq[2], NULL );
    
      return result;
    }
    
    static unsigned int N( unsigned int n )
    { 
      if ( n == 1 ) return 1;
    
      // n * log10(phi) - log10(sqrt(5)) + 1
      return n * 0.2089876402499787 - 0.3494850021680093 + 1.0; 
    }
    
    static void test_seq ( unsigned int n )
    {
      mpz_t result;
    
      mpz_init ( result );
    
      for ( unsigned int i = 1; i <= n; i++ )
        // fib(n) = F(n) N(n)
        gmp_printf ( "fib(%u): %Zd %u\n", i, fib ( i, &result ), N(i) );
    
      mpz_clear( result );
    }
    
    static void test_single ( unsigned int x )
    {
      mpz_t result;
    
      mpz_init ( result );
    
      // fib(n) = F(n) N(n)
      gmp_printf ( "fib(%u): %Zd %u\n", x, fib ( x, &result ), N(x) );
    
      mpz_clear( result );
    }
    
    int main( void )
    {
      // test sequence (first 100 #'s).
      test_seq ( 100 ); putchar( '\n' );
    
      // test single (4781st and 4782nd fibonacci #s).
      test_single ( 4781 ); putchar( '\n' );
      test_single ( 4782 );
    
      return EXIT_SUCCESS;
    }
    Code:
    $ cc -O2 fib.c -o fib.o -lgmp
    $ ./fib
    fib(1): 1 1
    fib(2): 1 1
    fib(3): 2 1
    fib(4): 3 1
    fib(5): 5 1
    fib(6): 8 1
    fib(7): 13 2
    fib(8): 21 2
    fib(9): 34 2
    fib(10): 55 2
    fib(11): 89 2
    fib(12): 144 3
    fib(13): 233 3
    fib(14): 377 3
    fib(15): 610 3
    fib(16): 987 3
    fib(17): 1597 4
    fib(18): 2584 4
    fib(19): 4181 4
    fib(20): 6765 4
    fib(21): 10946 5
    fib(22): 17711 5
    fib(23): 28657 5
    fib(24): 46368 5
    fib(25): 75025 5
    fib(26): 121393 6
    fib(27): 196418 6
    fib(28): 317811 6
    fib(29): 514229 6
    fib(30): 832040 6
    fib(31): 1346269 7
    fib(32): 2178309 7
    fib(33): 3524578 7
    fib(34): 5702887 7
    fib(35): 9227465 7
    fib(36): 14930352 8
    fib(37): 24157817 8
    fib(38): 39088169 8
    fib(39): 63245986 8
    fib(40): 102334155 9
    fib(41): 165580141 9
    fib(42): 267914296 9
    fib(43): 433494437 9
    fib(44): 701408733 9
    fib(45): 1134903170 10
    fib(46): 1836311903 10
    fib(47): 2971215073 10
    fib(48): 4807526976 10
    fib(49): 7778742049 10
    fib(50): 12586269025 11
    fib(51): 20365011074 11
    fib(52): 32951280099 11
    fib(53): 53316291173 11
    fib(54): 86267571272 11
    fib(55): 139583862445 12
    fib(56): 225851433717 12
    fib(57): 365435296162 12
    fib(58): 591286729879 12
    fib(59): 956722026041 12
    fib(60): 1548008755920 13
    fib(61): 2504730781961 13
    fib(62): 4052739537881 13
    fib(63): 6557470319842 13
    fib(64): 10610209857723 14
    fib(65): 17167680177565 14
    fib(66): 27777890035288 14
    fib(67): 44945570212853 14
    fib(68): 72723460248141 14
    fib(69): 117669030460994 15
    fib(70): 190392490709135 15
    fib(71): 308061521170129 15
    fib(72): 498454011879264 15
    fib(73): 806515533049393 15
    fib(74): 1304969544928657 16
    fib(75): 2111485077978050 16
    fib(76): 3416454622906707 16
    fib(77): 5527939700884757 16
    fib(78): 8944394323791464 16
    fib(79): 14472334024676221 17
    fib(80): 23416728348467685 17
    fib(81): 37889062373143906 17
    fib(82): 61305790721611591 17
    fib(83): 99194853094755497 17
    fib(84): 160500643816367088 18
    fib(85): 259695496911122585 18
    fib(86): 420196140727489673 18
    fib(87): 679891637638612258 18
    fib(88): 1100087778366101931 19
    fib(89): 1779979416004714189 19
    fib(90): 2880067194370816120 19
    fib(91): 4660046610375530309 19
    fib(92): 7540113804746346429 19
    fib(93): 12200160415121876738 20
    fib(94): 19740274219868223167 20
    fib(95): 31940434634990099905 20
    fib(96): 51680708854858323072 20
    fib(97): 83621143489848422977 20
    fib(98): 135301852344706746049 21
    fib(99): 218922995834555169026 21
    fib(100): 354224848179261915075 21
    
    fib(4781): 6613373228392440205294487620614988386258221854077091215085409985946829045853085401986203993473304704006532806
    665409928104132735658329269179943987136387182300044717764131511463189091855894347709734618375860803189410369063758088189
    877894296262173666162615798908603690555558947325195489010401576042985467429576660968458094630211279995925685576363846904
    620923411240924012459111166676397046505857634765545946568146469207985437550419934725555057011571432907392898446887608950
    757495331309532870809346002053423269043982163429046421434100265824395962789799611665560379134141747565790688021683374133
    609185679379451019521239667447805794754000569384184420297941428569052514865260289460639397278341955753541734004547198148
    295065866014920131004687808521408360211098208602574949093876196565133643939902372897823427134239526495052743368116407902
    737408752066026345832270977921462308832684229659932304926576303383449677677762164972960166123166928404793066801877376089
    10337658122657075262622220319456797676633847360981 999
    
    fib(4782): 1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694
    888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553
    966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792
    235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470
    911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665
    796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083
    544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723
    562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820
    492520348473874384736771934512787029218636250627816 1000
    For N(n)=1000, n is:
    Code:
    n = ceil( ( N + log10( sqrt(5) ) - 1 ) / log10(phi) ) =
    ceil( (1000 + 0.3494850021680093 - 1.0) / 0.2089876402499787 ) = 4782
    This is the same as john.c's second equation.
    Last edited by flp1969; 05-29-2023 at 02:08 PM.

  5. #5
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    thanks for that both of you i clearly was on the wrong track yesterday producing the spreadsheet

    @ john.c on line 13 you have a for loop with 1000000000000000lu as the limiter what does the lu do? i see that you have a typedef for ul as unsigned long but cant see where ul came from.

    @flp is gmp a standard library I cant find it in the header file directory... Do I need to download it?

    once again many thanks for the input

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,652
    lu just ensures that the numeric literal is interpreted as an unsigned long. Its not really needed and has no connection to the typedef.

    On Debian-type linux systems you can install the GNU Multiple Precision Arithmetic Library like this:
    sudo apt-get install libgmp-dev

    At a minimum this will add gmp.h and libgmp.a (or whatever).
    The actual library is the .a file.
    The .h file is the header that goes along with it and that you include in your .c file.
    When you compile a program using the library you need to "link" to the library. With gcc you would add -lgmp at the end of the command.

    Here's a very simple program to print the Nth fib.
    Code:
    // gcc -std=c11 -Wall -Wextra -Wpedantic -O2 -o fib fib.c -lgmp
    #include <stdlib.h>
    #include <gmp.h>
     
    int main(int argc, char **argv) {
        if (argc != 2) {
            gmp_printf("Usage: fib Nth\n");
            return 0;
        }
        int n = atoi(argv[1]);
     
        mpz_t a, b, c;
        mpz_inits(a, b, c, NULL); // allocates memory and inits values to 0
        mpz_set_ui(b, 1);
     
        for (int i = 0; i < n; ++i) {
            mpz_add(c, a, b);
            mpz_swap(a, b); // swaps are extremely efficient
            mpz_swap(b, c);
        }
     
        gmp_printf("%Zu\n", a);
     
        mpz_clears(a, b, c, NULL); // free memory
     
        return 0;
    }
    And that's the world in a nutshell, an appropriate receptacle.

  7. #7
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    "Project Euler problems are not so much programming problems as math problems"

    In that spirit, out-sourcing the heavy lifting to an external arbitrary precision libraries defeats most of the purpose, and removes most of the fun, learning and insight that can be gained.

    I had a crack at doing something like the OP's aim, with only using putchar() from the standard library:

    Code:
    #include <stdio.h>
    
    
    #define LENGTH 1000
    
    
    void print_num(char *num) {
       int j = 0;
       while(j < LENGTH-1 && num[j] == '0') {
          j++;
       }
       while(j < LENGTH) {
          putchar(num[j]);
          j++;
       }
       putchar('\n');
    }
    
    
    void add_on(char *result, char *to_add) {
        int carry = 0;
        for(int i = LENGTH-1; i >= 0; i--) {
          char total = result[i]+ (to_add[i]-'0') + carry;
          if(total > '9') {
             result[i] = total-10;
             carry = 1;
          } else {
             result[i] = total;
             carry = 0;
          }
        }
    }
    
    
    int main(int argc, char *argv[])
    {
        char num1[LENGTH], num2[LENGTH];
        for(int i = 0; i < LENGTH; i++) {
           num1[i] = '0';
           num2[i] = '0';
        }
        // Starting point
        num2[LENGTH-1] = '1';
    
    
        // Loop to add numbers
        while(num1[0] == '0' && num2[0] == '0') {
            add_on(num1,num2);
            print_num(num1);
            if(num1[0] != '0') {
                break;
            }
    
    
            add_on(num2,num1);
            print_num(num2);
            if(num2[0] != '0') {
                break;
            }
        }
    }

  8. #8
    Registered User
    Join Date
    Dec 2017
    Posts
    1,652
    In that spirit, out-sourcing the heavy lifting to an external arbitrary precision libraries defeats most of the purpose
    Well duh!
    And that's the world in a nutshell, an appropriate receptacle.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 04-07-2020, 01:46 AM
  2. Replies: 2
    Last Post: 10-31-2009, 06:49 PM
  3. Adding a Large number digit by digit
    By mejv3 in forum C Programming
    Replies: 23
    Last Post: 09-21-2007, 03:00 PM
  4. Adding a Large number digit by digit
    By mejv3 in forum C Programming
    Replies: 1
    Last Post: 09-14-2007, 03:28 AM
  5. outputs number digit by digit
    By Unregistered in forum C++ Programming
    Replies: 14
    Last Post: 05-17-2002, 04:43 PM

Tags for this Thread