1

任意のサイズの符号なし整数 (バイナリ形式で格納されている) を 10 進数に変換するアルゴリズムが必要です。つまり、人間が読めるようにするためです ;)
現在、10 の除算によるモジュラスと剰余を継続的に計算する、おそらく (または明らかに) やや素朴な方法を使用しています。
残念ながら、速度はやや... ラメです。

たとえば、2000^4000 を (bignum ライブラリを使用して) 計算すると、約 1.5 秒かかります (炎上しないでください xD)。ただし、必要な基本変換を含む印刷には約 15 分かかり、かなり面倒です。

私は bc をテストしましたが、これは両方を 1 秒未満で実行します。
それはどのように行うのですか？（fftsを使用した乗算や、基数変換のみではありません）

4

3 に答える 3

2

私は現在、モジュラスと剰余を 10 で除算して連続的に計算する、多分 (または明らかに) やや素朴な方法を使用しています。
そうすれば、O(n^2)複雑さが増し、15 分よりもはるかにうまくいくはずです。

ただし、 による除算を正確に行う方法は一見の価値があります10。

  1. long による long の一般的な除算ではなく、標準の long 数による除算のより単純なアルゴリズムを適用するようにしてください。
  2. メモリを再利用するようにしてください。10Kb ブロックを 10000 回割り当てると、確実にパフォーマンスが低下します。

edit
long 2 進数を 1 回のパスで 10 で除算し、結果とリマインダーの両方を取得する方法。追加メモリなし。
簡単な疑似コード (a[0]は最上位桁)

int r = 0;
for (int i = 0; i < n; ++i) {
    r = r * 2 + a[i];
    a[i] = r / 10;
    r = r % 10;
}

number の例を見てみましょう100111011 = 315。

ステップ 0:r = 1, a[0] = 0
ステップ 1:r = 2, a[1] = 0
ステップ 2:r = 4, a[2] = 0
ステップ 3:r = 9, a[3] = 0
ステップ 4:r = 9, a[4] = 1
ステップ 5:r = 9, a[5] = 1
ステップ 6:r = 8, a[6] = 1
ステップ 7:r = 7, a[7] = 1
ステップ 8:r = 5, a[8] = 1

したがって、リマインダーは5で、結果は000011111 = 31です。

于 2011-01-07T17:48:18.053 に答える
1

bc は 2 ではなく 10^n を基数として使用していると思います。そのため、すべての内部「桁」は 10 進数の n 桁であり、少なくとも 10 進数の入出力では問題は簡単になります。

于 2011-01-07T18:28:27.093 に答える
0

べき乗を使用する必要はありません。

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int main(){
    char a[] = "10011";
    unsigned long int res= 0;
    int i;

    for(i = 0; i < strlen(a); i++){
        res = (res<<1) + (a[i]-'0');
    }

    printf("%d",res);
    return 0;
}

最初の更新

これで長さは問題ないはず…

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

char *doubles(char *);
char *sum(char *,int);

int main(){
    char a[] = "10011";
    char *res = calloc(2,sizeof(char));
    int i;

    res[0] = '0';
    for(i = 0; i < strlen(a); i++){
        res = sum(doubles(res),(a[i]-'0'));
    }

    printf("%s",res);
    return 0;
}

char *doubles(char *s){
    int i,len = strlen(s),t = 0;
    char *d;
    d = calloc(len+1,sizeof(char));
    for(i = 0; i < len; i++){
        t = ((s[len-i-1]-'0')<<1) + t;

        d[len-i] = ('0' + (t%10));
        t = t/10;
    }

    d[0] = t+'0';

    return (d[0] == '0')?d+1:d;
}

char *sum(char *s,int n){
    int i, len = strlen(s),t = n;
    char *d = calloc(len+1,sizeof(char));

    for(i = 0; i < len ; i++){
        t = (s[len-i-1]-'0') + t;
        d[len-i] = ('0' + (t%10));
        t = t/10;
    }
    d[0] = t+'0';

    return (d[0] == '0')?d+1:d;
}
于 2011-01-07T17:35:44.320 に答える