OT Programmazione - rolling release - chunk 1 2015

[MItaly]

Sì mi era stato detto che era da Project Euler, per come mi era stato specificato si intendeva la semplice somma in base 10 (sostanzialmente, quello che viene fuori se in Python fai sum(int(x) for x in str(2**1000)), o se vogliamo il 1000° elemento della sequenza A001370 ).

Una soluzione valida e compatta è semplicemente:

#include <stdio.h>
#include <math.h>

int main(int argc, const char *argv[]) {
    char buf[400];
    int total = 0, i;
    sprintf(buf, "%.0f", pow(2., 1000));
    for (i=0; buf[i]; i++) {
        total += buf[i] - '0';
    }
    printf("%i\n", total);
    return 0;
}

La parte divertente è che se uno trovasse questo codice in giro "per davvero" verrebbe il dubbio se l'ha scritto un principiante che non ha capito nulla di floating point ma gli è andata bene oppure un esperto che sa esattamente quello che sta facendo. Io stesso quando mi è stato mostrato ci sono rimasto qualche secondo ("ma questo non si può fare!") prima del momento "a-ha!".

(sul population count e un altro po' di algoritmi bitwise "magici" invece avevo trovato un po' di tempo fa questa gustosa paginetta, in cui c'è anche qualche spiegazione interessante; purtroppo non ho ancora avuto modo di applicarli direttamente)

[M.A.W. 1968]

(sul population count e un altro po' di algoritmi bitwise "magici" invece avevo trovato un po' di tempo fa questa gustosa paginetta, in cui c'è anche qualche spiegazione interessante; purtroppo non ho ancora avuto modo di applicarli direttamente)

Sugli algoritmi bitwise c'è una discreta mole di letteratura, soprattutto (com'è ovvio) in ambito embedded, dall'ormai introvabile Cavanagh degli anni Settanta (a cavallo tra implementazioni su silicio e algoritmica) a vari paragrafi del TAoCP di Knuth, dal divertente "Hacker's delight" a "Matters computational" con relativa libreria FXT, fino al folklore matematico diffuso su molti forum tipo AVRfreaks dove certi "trucchi" come trasformare a runtime un piccolo intero n in 2^n con una manciata di istruzioni Assembly RISC loopless sono davvero all'ordine del giorno. Anche perché, oltre ai vari idiomi, è davvero importante comprendere i meccanismi dell'algebra dei campi finiti di ordine due, che ha una ricca pletora di peculiarità irriproducibili in altri casi.