Thread: anything that can handle a 1000 digit number

Use libgmp if you want to deal with big numbers...

And, since:

It's easy to demonstrate that a nth Fibonaacci number N(n) algarisms given by:

PS: The previous equation to N() was wrong.

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;
}

Yep... john.c is right. Actualy, the equation to calculate the number of decimal algarisms from F(n) is:



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.

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;
}

In that spirit, out-sourcing the heavy lifting to an external arbitrary precision libraries defeats most of the purpose

Well duh!