projecteuler-16.c

// https://projecteuler.net/problem=16
//
// to build:
// cc -lgmp projecteuler-16.c -o projecteuler-16
//
// in response to:
// https://boards.4channel.org/g/thread/70641542#p70645151
// https://boards.4channel.org/g/thread/70641542#p70644975
//
// libgmp is one of the most famous BigInt libraries
// gcc itself is compiled with either libgmp or mpfr
// https://stackoverflow.com/questions/9450394/how-to-install-gcc-piece-by-piece-with-gmp-mpfr-mpc-elf-without-shared-libra
//
// the easy way to do BigInt euler problems is to code in a language with builtin BigInts,
// Common Lisp, Ruby, Python, some versions of Lua (not LuaJIT), etc.
//
// we demonstrate a crude special purpose solution in plain C (not full implementation)
// then repeat same method using GMP BigInts (probably slower actually, but only in special case).

#include <stdio.h>
#include <gmp.h> // apt get libgmp-dev

#define ENOUGH 512 // 300-something would be enough...

int CrudeInt[ENOUGH] = {0};

void crude_x2() {
    int tmp;
    int carry = 0;
    for(int i = 0; i < ENOUGH; i++) {
        tmp = 2*CrudeInt[i] + carry;
        carry = tmp / 10;
        tmp = tmp % 10;
        CrudeInt[i] = tmp;
    }
    return;
}

int crude_sum_digits() {
    int acc = 0;
    for(int i = 0; i < ENOUGH; i++) acc += CrudeInt[i];
    return acc;
}

int main() {
    // CrudeInt[] and related functions defined above
    int CrudeSum;

    mpz_t GmpSum;
    mpz_t BigInt;
    mpz_t bigtmp;

    CrudeInt[0] = 2; // this is 2^1
    for(int i = 1; i < 1000; i++) crude_x2();
    CrudeSum = crude_sum_digits();

    // https://www.cs.colorado.edu/~srirams/courses/csci2824-spr14/gmpTutorial.html
    // https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test
    // ...
    // search for (with quotes): "#include <gmp.h>" site:pastebin.com/
    // google, bing, duckduckgo support the "site:" search operator

    mpz_init(GmpSum); mpz_init(BigInt); mpz_init(bigtmp);
    mpz_set_ui(BigInt, 2);
    for(int i = 1; i < 1000; i++) mpz_mul_ui(BigInt, BigInt, 2);

    while(mpz_cmp_ui(BigInt, 0) != 0) {
        mpz_mod_ui(bigtmp, BigInt, 10);
        mpz_add(GmpSum, GmpSum, bigtmp); // all bigints this time, no "_ui" suffix
        mpz_div_ui(BigInt, BigInt, 10);
    }

    printf("CrudeSum: %d\n", CrudeSum);
    gmp_printf("GmpSum  : %Zd\n", GmpSum);

    mpz_clear(GmpSum); mpz_clear(BigInt); mpz_clear(bigtmp);
    return 0;
}