将十六进制数流化为十进制

Question

我想使用 BBP 公式在 C 程序的 pthread 进程中计算 Pi，而另一个进程则尽可能打印结果。然而，BBP 给出了一个基数 16 的答案，而我想向用户传输一个基数 10 的答案。

如何确定打印 10 基数转换为 16 基数的第 n 位数字是否安全？

提前致谢！

Answer 1

一个解决方案是测试是否增加了当前可用的最后十六进制数字是否更改了您正在考虑显示的十进制数字。

考虑具有十六进制表示的x ... H _{3 h 2 h 1 h 0 .h <子> -1 h -2 ...和十进制表示... d 3 d 2 d 1 d 0 .d -1 d -2 ...}

假设我们有一个截断的数字，使我们只知道来自h _{∞到h j 的数字。让y成为这些数字表示的数字。设Z为y + 16 ^{j ，在j数字位置中是y加一个。 然后x的值可能是来自y（包含）到z（独占）的任何值。}}

现在考虑候选十进制数字，数字d _{∞到d i 。让Y'是这些数字表示的数字。让z'是y + 10 ^{i 。 iff y'≤y和z≤z'，然后十进制数字d ∞ to d i 必须是x的完整十进制数字的前缀（即，这些已知十进制数字以十进制数字为x;它们不会随着发现的十六进制数字而变化）。}}

这是因为可以通过向y添加一些零或正值来形成x的值，并且所需的值小于i数字位置的值小于1。相反，如果不平等不保持，则x可能超出候选数字跨越的间隔。

Answer 2

@Eric Postpischil 发布了一个很好的通用算法。

在实现OP目标的过程中，可以走一些捷径。
单独处理 Pi 的整数部分，只处理小数部分。
假设输入是以 16 为基数，然后每次添加 1 位。

实施注意事项：
我通过使用固定内存分配和字节数组（字符串）处理来作弊。当然，人们会保存数组长度而不是 strlen() 并使用字节 0 - 9 而不是字符“0”到“9”，但这很快就被混在一起了，这样更容易调试。数组大小 s/b 是动态的，但很容易添加。

#include <assert.h>
#include <memory.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  char *Sum;
  char *Add;
} Pi_T;

void Pi_Print(const char *Title, Pi_T *State) {
  printf("%s\n", Title);
  printf("  Sum: '%s'\n", State->Sum);
  printf("  Add: '%s'\n", State->Add);
}

// Sum += Add
void Pi_Add(char *Sum, char *Add) {
  size_t LenS = strlen(Sum);
  size_t LenA = strlen(Add);
  while (LenS > LenA) {
    Add[LenA++] = '0';
    Add[LenA] = '\0';
  }
  while (LenA > LenS) {
    Sum[LenS++] = '0';
    Sum[LenS] = '\0';
  }
  unsigned Accumulator = 0;
  while (LenA > 0) {
    LenA--;
    Accumulator += Add[LenA] - '0';
    Accumulator += Sum[LenA] - '0';
    Sum[LenA] = Accumulator % 10 + '0';
    Accumulator /= 10;
    assert(Accumulator <= 9);
  }
  assert(Accumulator == 0);
}

// Divide the `Add` by 2
void Pi_Div2(char *Add) {
  size_t LenS = strlen(Add);
  size_t i;
  unsigned Accumulator = 0;
  for (i = 0; i < LenS; i++) {
    Accumulator += Add[i] - '0';
    Add[i] = Accumulator / 2 + '0';
    Accumulator %= 2;
    Accumulator *= 10;
    assert ((Accumulator == 0) ||  (Accumulator == 10));
  }
  if (Accumulator > 0) {
    Add[i++] = Accumulator / 2 + '0';
    Add[i] = '\0';
    Accumulator %= 2;
    Accumulator *= 10;
    assert(Accumulator == 0);
  }
}

void Pi_PutHex(Pi_T *State, unsigned HexDigit) {
  // Add HexDigit, 1 bit at a time.
  for (unsigned i = 4; i-- > 0;) {
    if (HexDigit & (1 << i)) {
      Pi_Add(State->Sum, State->Add);
    }
    // Should the Sum[0] be extracted?
    if (State->Add[0] == '0') {
      for (size_t i = 1; State->Sum[i] && State->Add[i]; i++) {
        unsigned Accumulator = State->Sum[i] - '0' + State->Add[i] - '0';
        if (Accumulator > 9)
          break;
        if (Accumulator < 9) {

          // !!!!!!!!!!!!!!!!!!!!!!!!!!!!
          // Print the decimal digit!
          printf("%c", State->Sum[0]);
          // !!!!!!!!!!!!!!!!!!!!!!!!!!!!

          memmove(&State->Sum[0], &State->Sum[1], strlen(State->Sum));
          memmove(&State->Add[0], &State->Add[1], strlen(State->Add));
          break;
        }
      }
    }
    Pi_Div2(State->Add);
  }
}

void Pi_Test(void) {
  Pi_T State;
  State.Sum = malloc(500);
  State.Add = malloc(500);
  State.Sum[0] = '\0';
  State.Add[0] = '5';
  State.Add[1] = '\0';
  // http://calccrypto.wikidot.com/math:pi-hex
  static const char *pi = "3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89452821E638D01378";
  // http://www.miniwebtool.com/first-n-digits-of-pi/?number=100
  // 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
  // Output
  // 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117
  const char *p = &pi[2];
  // Pi_Print("Init", &State);
  printf("3.");
  // add each hex digit, one at a time.
  while (*p) {
    unsigned HexDigit = (*p <= '9')  ? (*p - '0') : (*p - 'A' + 10);

    // !!!!!!!!!!!!!!!!!!!!!!!!!!!!
    // Put in the hexadecimal digit
    Pi_PutHex(&State, HexDigit);
    // !!!!!!!!!!!!!!!!!!!!!!!!!!!!

    p++;
  }
  printf("\n");
  // Pi_Print("End", &State);
}