Преобразуйте шестнадцатеричное число в десятичное
Вопрос
Я хотел бы использовать формулу BBP для вычисления Pi в процессе pthread C-программы, в то время как другой процесс печатает результат, насколько это возможно.Однако BBP дает базовый ответ 16, в то время как я хотел бы передать пользователю базовый ответ 10.
Как я могу определить, безопасно ли печатать n-ю цифру числа по основанию 10, преобразованного по основанию 16?
Заранее спасибо!
Решение
Одним из решений - проверять, увеличивается ли увеличение последней шестнадцатеричной цифры в настоящее время, изменяет десятичную цифру, которую вы рассматриваете отображать.
Рассмотрим число x с шестнадцатеричным представлением ... h 3 h 2 h 1 h 0 .h < sub> -1 h -2 ... и десятичное представление ... d 3 d 2 d 1 d 0 .d -1 d -2 ...
Предположим, у нас есть усеченный цифр, так что мы знаем только цифры от h ∞ h j . Пусть y - число, представленное этими цифрами. Пусть z y + 16 j , который y плюс один в положении j-знака. Тогда значение x может быть любое значение из y (включено) на z (эксклюзив).
Теперь рассмотрим кандидат десятичный цифр, с цифрами d ∞ до d i . Пусть y 'быть числом, представленным этими цифрами. Пусть z - y + 10 i . Iff y '≤ y и z ≤ z', то десятичные цифры d ∞ d i должны быть префиксом полного десятичного числа для x (то есть они Известно, что десятичные цифры появляются в десятичной цифре для X; они не будут изменяться как обнаружены более шестнадцатеричные цифры).
Это связано с тем, что значение X, находящееся в [y, z), может быть сформировано путем добавления некоторого нуля или положительного значения на Y ', и что требуемое значение меньше 1 в положении I цифры. И наоборот, если неравенство не удерживают, то X может быть за пределами интервала, который сканирует цифры кандидата.
Другие советы
@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);
}