문제
C-Program의 PThead 프로세스에서 PI를 계산하려면 BBP 공식을 사용하여 다른 프로세스가있는 한 결과를 인쇄합니다.그러나 BBP는 사용자에게 기본 10 답변을 스트리밍하고자하는 동안 기본 16 답변을 제공합니다.
기본 10 변환 된베이스 16 번호의 n 번째 숫자를 인쇄하는 것이 안전한 지 확인할 수 있습니까?
미리 감사드립니다!
해결책
하나의 해결책은 현재 사용 가능한 마지막 16 진수의 증가가 표시되는 소수 자릿수를 변경하는지 여부를 테스트하는 것입니다.
3 h 2 h 1 h 0 .h 3 h 3 h. 하위> -1 h -2 ... 및 10 진수 표현 ... D 3 d 2 d 1 d 0 .d -1 d -2 ...
우리는 H ∞ 에서 h j 로 숫자 만 알고 있기 때문에 잘린 숫자를 가지고 있다고 가정합니다. y 가이 숫자로 표시되는 숫자가되도록하십시오. z가 y + 16 j 를 줌으로하자. 그런 다음 x 값은 y (포함)에서 z (exclusive)까지의 값일 수 있습니다.
이제 숫자 D ∞ 을 d i 로 사용하여 후보핵 숫자를 고려하십시오. y '가이 숫자로 표시된 숫자가되도록하십시오. z 'y + 10 i 을 가자. IFF Y '≤ Y 및 Z ≤ Z', DEMITS DITS D ∞ ~ D I 는 X에 대한 완전한 10 진수 숫자의 접두사 여야합니다 (즉, 소수 자릿수는 x의 십진수 숫자에 나타나는 것으로 알려져 있습니다. 더 많은 16 진수가 발견됨에 따라 변경되지 않음).
[Y, Z)에있는 X 값은 0 또는 양의 값을 y '에 추가하고 필요한 값은 i 디지트 위치에서 1보다 작 으면 형성 할 수 있기 때문입니다. 반대로 불평등이 유지되지 않으면 X는 후보 자릿수가 스팬 된 간격을 벗어날 수 있습니다.
다른 팁
@eric postpischil은 미세한 범용 알고리즘을 게시했습니다.
OP 목표를 구현하는 경우, 일부 짧은 컷이 실현 될 수 있습니다.
PI의 정수 부분을 다루고 분수를 다루십시오.
입력이 기본 16이고 한 번에 1 비트를 추가하십시오.
구현 메모 :
고정 메모리 할당 및 바이트 배열 (문자열) 처리를 사용하여 속임수를 썼습니다.확실히 하나는 strlen()
가 아닌 배열 길이를 저장하고 char '0'이 아닌 바이트 0 - 9를 '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);
}
.