Numero esagonale del flusso come decimale

Question

Vorrei utilizzare la formula BBP per calcolare PI nel processo del pthread del programma C, mentre un altro processo stampa il risultato per quanto ne abbia.Tuttavia BBP fornisce una base a 16 risposte mentre vorrei trasmettere una base di una base 10 rispondi all'utente.

Come posso determinare se è sicuro stampare la cifra N-TH di una base da 10 base convertita di base 16?

Grazie in anticipo!

Answer 1

Una soluzione è verificare se aumentere l'ultima cifra esadecimale attualmente disponibile cambia la cifra decimale che stai considerando la visualizzazione.

Considera un numero X con la rappresentazione esadecimale ... h _{3 h 2 h 1 h 0 .h < Sub> -1 h -2 ... e rappresentazione decimale ... d 3 d 2 d 1 d 0 .d -1 d -2 ...}

Supponiamo di avere un numero troncato, in modo che conosciamo solo le cifre da h _{∞ a h j . Sii il numero rappresentato da queste cifre. Lascia che Z sia y + 16 ^{j , che è y più uno nella posizione di Digit J. Quindi il valore di X potrebbe essere qualsiasi valore da Y (incluso) a Z (esclusivo).}}

Ora considera un numero decimale candidato, con cifre d _{∞ a d i . Sia y 'essere il numero rappresentato da queste cifre. Sia Z 'Be y + 10 ^{i . IFF Y '≤ Y E Z ≤ Z', quindi le cifre decimali D ∞ a D I deve essere un prefisso del numero decimale completo per X (cioè questi Le cifre decimali sono note per apparire nel numero decimale per X; non cambieranno come vengono scoperte più cifre esadecimali).}}

Questo perché il valore di X, essendo in [Y, Z) può essere formato aggiungendo un valore zero o positivo a y 'e quel valore necessario è inferiore a 1 nella posizione di Digit I. Viceversa, se le disuguaglianze non tengono, X potrebbero essere al di fuori dell'intervallo anch'esso andato da parte delle cifre del candidato.

Answer 2

@eric PostPischil ha pubblicato un algoritmo di perdi raffinati.

Nell'attuazione dell'obiettivo OP, alcuni tagli cortocircuiti possono essere realizzati.
Gestire la parte intera del PI separato e affronta solo la frazione.
Assumere l'ingresso è base 16 e quindi aggiungi 1 bit alla volta.

Note di implementazione:
Ho ingannato utilizzando la maneggevolezza di assegnazione a memoria fissa e byte-array (stringa).Certamente uno salvarebbe la lunghezza dell'array piuttosto che strlen() e utilizzare Byte 0 - 9 piuttosto che Char '0' a '9', ma questo è stato gettato insieme in modo rapido ed era più facile da eseguire il debug in questo modo.Dimensione dell'array S / B Dynamic, ma è facile da aggiungere.

#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);
}

.