如何将数字字符串存储为任意大整数？

Question

设ib为输入基数，ob为输出基数。 str 是某个任意大整数 x 的 ASCII 表示。我需要定义 f 例如：

f(str="1234567890", ib=10, ob=16) = {4, 9, 9, 6, 0, 2, 13, 2}

... 其中 f 的 return 类型是一个 int 数组，其中包含该整数的 ob 基数。我们假设 2 >= ob <= MAX_INT 和 2 >= ib <= 10，以及 str 将始终是一个有效的字符串（不需要否定）。

Answer 1

我用旧规范写了这篇文章，所以它不再有效，但它可能作为一个起点很有用。

代码可以处理 long long 个震级。在 C 中实现任意精度数字是一个巨大的飞跃！

请注意使用 -1 而不是 0 作为结束标记。可以接受从 2 到 36 的 ib 和任何 ob.

包括示例 main。

函数 f 不是可重入的。为了使其线程安全，它可以分配所需的内存，然后 return 指向它的指针。最简单的协议是让调用者负责之后释放内存。

#include <stdlib.h>
#include <limits.h>
#include <stdio.h>

int *f(const char *str, int ib, int ob) {
    static int result[CHAR_BIT * sizeof(long long) + 1];
    int i = sizeof(result) / sizeof(int) - 1;
    long long l = strtoll(str, NULL, ib);
    result[i--] = -1;
    while (l) {
        result[i] = l % ob;
        l /= ob;
        i--;
    }
    return result + i + 1;
}

int main()
{
    int *x = f("1234567890", 16, 10);
    while (*x > -1) {
        printf("%d ", *x);
        x++;
    }
    return 0;
}

Answer 2

一些东西可以让 OP 开始，但足以让 OP 享受编码体验。

// form  (*d) = (*d)*a + b
static void mult_add(int *d, size_t *width, int ob, int a, int b) {
    // set b as the carry
    // for *width elements,
    //   x = (Multiply d[] by `a` (using wider than int math) and add carry)
    //   d[] = x mod ob
    //   carry = x/ob
    // while (carry <> 0)
    //   widen d
    //   x =  carry
    //   d[] = x mod ob
    //   carry = x/ob
}

int *ql_f(const char *src, int ib, int ob) {
  // Validate input
  assert(ib >= 2 && ib <= 10);
  assert(ob >= 2 && ob <= INT_MAX);
  assert(src);

  // Allocate space
  size_t length = strlen(src);
  // + 2 + 4 is overkill, OP to validate and right-size later
  size_t dsize = (size_t) (log(ib)/log(ob)*length + 2 + 4);   
  int *d = malloc(sizeof *d * dsize);
  assert(d);

  // Initialize d to zero
  d[0] = 0;
  size_t width = 1;
  while (*src) {
    mult_add(d, &width, ob, ib, *src - '0');
    src++;
  }

  // add -1 to end, TBD code

  return d;
}

如何将数字字符串存储为任意大整数？

How to store a digit string into an arbitrary large integer?

c

math

digits

arbitrary-precision