Вид для печати
Если совсем грубо, то вероятность появления "цифры" означающей 9999 - порядка 1/10000, да еще и перенос должен быть из следующего разряда, то есть вероятность около 1/100К, поэтому ошибка от 100К знаков может вылезти. Это если она там есть (вдруг ряд сходится так быстро что перенос не возникает), пока это только мое подозрение.Цитата:
Сообщение от ivagor
http://bio.fizteh.ru/student/spravoc...rpfelw5bsu.zip
999999,пятаяседьмая строка
Если верить архиву с миллиардом знаков числа пи, который скачал на рутракере, та программа правильно считает максимум 16256 знаков (за 1.7 секунды). Для 8биток выше крыши
- - - Добавлено - - -
Если заменить long на int64_t, то правильно считает до 54932 знака включительно (за 25 секунд).
Смущает. Там есть одна хитрость, которая позволит ускорить наш spigot ( уже наш :) ) ровно в два раза.Цитата:
Сообщение от ivagor
- - - Добавлено - - -
Может просто тупо тот алгоритм на асме переписать? Хотя, основная масса времени это всё равно умножение/деление, не думаю, что в сишном рантайме они какие-то неоптимальные.
- - - Добавлено - - -
Если только использовать не чисто 32-битные умножение/деление, а смешанные 32/16 битные. В том алгоритме явно указано, что нужно умножать uint32 на uint32, ну и делить также. А на самом деле нужно uint16*uint16 -> uint32, а затем uint32/uint16 -> uint16.
У тебя есть готовые арифметические процедуры для 32 разрядных? Если да, то я за "тупое переписывание". Пусть даже будет медленнее, чем pirk20, зато больше цифр можно считать.Цитата:
Сообщение от b2m
У меня были процедурки для 32битных, но они, насколько помню, в архиве на другом компе, который сдох (но винт целый).
Ну и у нас ещё одно преимущество: вместо двух операций / и % мы делаем это за одну операцию. Фактически, тоже ускорение почти в два раза.
- - - Добавлено - - -
16*16 -> 32 вроде где-то было (FAT?), а вот деления точно не было. Но что нам стоит дом построить? :)Цитата:
Сообщение от ivagor
Была старинная математическая библиотека для 8080, но не могу вспомнить как назывался архив или хотя бы кто автор.
Возможно у vinxru есть готовые процедуры для 32-разрядных для его си?
Конечно можно и заново написать.
- - - Добавлено - - -
В Гуртовцеве Гудыменко есть готовые процедуры для 16*16=32 и 32/16
Вот это можно как-то ускорить (не разворачивая цикл)?
Код:MUL32: MOV B,H ; DEHL = DE*HL
MOV C,L
LXI H,0
MVI A,17
MUL321: DCR A
RZ
XCHG
DAD H
XCHG
JC MUL322
DAD H
JNC MUL321
INX D
JMP MUL321
MUL322: DAD H
JNC $+4
INX D
DAD B
JNC MUL321
INX D
JMP MUL321
Эх, для меня это все очень сложно, качать мегабайтные архивы, сверять :)Цитата:
Сообщение от ivagor
Есть путь попроще:
Сначала оно прикольно упало, когда я NUMS поставил 280000 :), стек коротковат оказался, пришлось static вкрутить.Код:#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <windows.h>
#define NUMS 280000
int main()
{
static long r[NUMS + 1];
long i, k;
long b, d;
long c;
long x;
c = 0;
for (i = 0; i < NUMS; i++)
r[i] = 2000;
for (k = NUMS; k > 0; k -= 14)
{
d = 0;
i = k;
while (1)
{
d += r[i] * 10000;
b = i * 2 - 1;
r[i] = d % b;
d /= b;
i--;
if (i == 0) break;
d *= i;
}
x = c + d / 10000;
if (x >= 10000)
{
printf("\r\nERROR (%d, %d)", x, k);
break;
}
printf("%.4d", (int)(c + d / 10000));
c = d % 10000;
}
return 0;
}
А потом оно секунд за 10 привело к ошибке:
ERROR (10000, 119266)
Ожидаем четыре цифры, а оказывается их пять, и пятая-то, вот досада, должна быть перенесена в уже выведенное, косяк-с, мда.
Итого - ошибка есть, возникает на 45-тысячной с копейками цифре, если кому надо меньше цифр (ограничен там восьмибитками или еще чего) - то и так сгодится
b2m, у меня по той процедуре идей нет. Обещаю не ударяться в паразитическую оптимизацию :), если что - ты сам потом оптимизируешь.
Vslav
У меня пока нет оснований не доверять тому архиву, т.ч. с 45000 я не согласен.Цитата:
Сообщение от ivagor