Нужен алгоритм для работы с большими числами

[michael]

Есть число, представленное в виде: n1*T1+f1, n1 - целое, T1 и f1 - вещественные, 0<=f1<T1. Нужно это число представить в другом виде: n2*T2+f2, условия на n2, T2 и f2 аналогичны вышеприведённым. T2 задано, n2 и f2 надо найти. Интересует больше f2, n2 не слишком актуально. Точность алгоритма не должна зависеть от n1, которое может быть очень большим.

[grub]

Лаба?

[michael]

Скорее часть докторской:)

[cympak]

Что-то это все мне напоминает школьное деление с остатком. Если так, то смотреть школьный учебник по математике за 3-4 класс

При известном T2 получаем n2=trunc((n1*T1+f1)/T2), f2=(n1*T1+f1) - (n2*T2)

Что-то как-то не тянет на докторскую...

[myst]

Можно это дело оформить на Python, который поддерживает числа произвольных размеров прямо из коробки. Работает достаточно быстро.

[michael]

Что-то это все мне напоминает школьное деление с остатком. Если так, то смотреть школьный учебник по математике за 3-4 класс

При известном T2 получаем n2=trunc((n1*T1+f1)/T2), f2=(n1*T1+f1) - (n2*T2)

Что-то как-то не тянет на докторскую...

Я же написал, что точность алгоритма не должна зависеть от n1. То, что вы предлагаете - тривиально и при больших n1 будет выдавать полную лажу.

python не нужен. Это просто часть большой задачи и переписывать придётся довольно много. И скорость нужна максимальная, а не достаточно быстрая. Как крайний вариант можно заюзать библиотеку gmp, но хотелось бы более красивое решение.

[myst]

1. Чем больше n1 тем больше точность. Мы же _умножаем_ на n1, а не делим. С другой стороны, о какой точности речь, если n2 -- _целое_ число?

2. Хочешь и на ёлку залезть и руки не ободрать? Не получится.

[cympak]

Так точность алгоритма и не зависит от n1, она зависит от того на сколько точны у вас операции сложения, умножения и деления .

Наверное перед решением таких задач стоило бы почитать классику... например Кнута ("Искусство программирования").

[Gnida]

http://forum.linux.by/viewtopic.php?t=8429

[michael]

Если я тупо умножу n1*T1 и прибавлю f1, то я потеряю примерно log10(n1) значащих цифр из f1. Естественно, при дальнейших операциях точность расти не будет. В итоге в f2 будет на log10(n1) значащих цифр меньше. То есть при таком подходе точность существенно зависит от n1. Очевидно, что задача имеет решение. Однако имеет ли она решение без использования вещественных чисел с произвольной точностью?

[myst]

Дружище, а кто сказал про FPU-числа? Если считать в другом формате, например в bc, то можно регулировать точность до какого угодно знака. И ничего теряться не будет. Выставь в bc scale=1000000 и живи спокойно. Только тормозить будет.

[michael]

Я говорил про FPU числа. Понятно, что с числами произвольной точности задача решается элементарно. Существует ли алгоритм, использующий только числа с плавающей точкой (ну, и целые тоже)? Да, можно заюзать gmp, но: 1) мне лень с ним разбираться, 2) это часто повторяющаяся операция и алгоритм нужен простой, чтобы не было потери в скорости.