Conversione di base di dimensioni illimitate?

Question

Sto cercando di implementare un tipo Bigint in JavaScript usando una serie di numeri interi. Per ora ognuno ha una limitazione superiore di 256. Ho finito di implementare tutte le operazioni intera, ma non riesco a capire come convertire il Bigint nella sua rappresentazione di stringa. Naturalmente, il modo semplice è questo:

BigInt.prototype.toString = function(base) {
    var s = '', total = 0, i, conv = [
        ,,
        '01',
        '012',
        '0123',
        '01234',
        '012345',
        '0123456',
        '01234567',
        '012345678',
        '0123456789',
        ,
        ,
        ,
        ,
        ,
        '0123456789abcdef'
    ];
    base = base || 10;

    for(i = this.bytes.length - 1; i >= 0; i--) {
        total += this.bytes[i] * Math.pow(BigInt.ByteMax, this.bytes.length - 1 - i);
    }

    while(total) {
        s = conv[base].charAt(total % base) + s;
        total = Math.floor(total / base);
    }

    return s || '0';
};

Ma quando i bigint ottengono effettivamente grande, Non sarò in grado di convertire aggiungendo più. Come posso convertire un array di base-X in un marsupio di base-y?

Answer 1

Vedi l'esempio che ho dato in questa risposta a una domanda simile di recente (è per la base-10 a Base-3, ma il principio dovrebbe essere trasferibile): C Base veloce Convertire da decimale in ternario.

In sintesi:

Iterazione sulle cifre di input, da basse a alte. Per ogni posizione di cifre, calcola prima ciò che 1000 ... 000 (base-256) sarebbe nella rappresentazione di uscita (è 256 volte la potenza precedente di 256). Quindi moltiplica quel risultato per cifre e accumula nella rappresentazione di uscita.

Avrai bisogno di routine che eseguono moltiplicazione e aggiunta nella rappresentazione di output. La routine di moltiplicazione può essere scritta in termini di routine di addizione.

Tieni presente che non sostengo che questo approccio sia in alcun modo veloce (penso che sia O (n^2) nel numero di cifre); Sono sicuro che ci sono approcci algoritmicamente più veloci di questo.

Answer 2

Se sei pronto a indossare il tuo limite di pensiero matematico più di me in questo momento, qualcuno sembra aver spiegato come convertire le rappresentazioni delle cifre usando il triangolo di Pascal:

http://home.ccil.org/~remlaps/dispconweb/index.html

Ci sono collegamenti al codice sorgente vicino al fondo. Sono in Java piuttosto che JavaScript, ma se stai facendo lo sforzo di ottenere la matematica, probabilmente puoi trovare la tua implementazione o impegnarsi per portare il codice ...