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

Все о программировании под *nix
michael
Неотъемлемая часть форума
Сообщения: 434
Зарегистрирован: 12 апр 2004, 11:00
Откуда: г. Владивосток
Контактная информация:

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

Сообщение michael »

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

Аватара пользователя
grub
Неотъемлемая часть форума
Сообщения: 849
Зарегистрирован: 13 сен 2006, 10:29
Откуда: Минск
Контактная информация:

Сообщение grub »

Лаба?
Змагайся і адпачывай!

michael
Неотъемлемая часть форума
Сообщения: 434
Зарегистрирован: 12 апр 2004, 11:00
Откуда: г. Владивосток
Контактная информация:

Сообщение michael »

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

Аватара пользователя
cympak
Увлекающийся
Сообщения: 114
Зарегистрирован: 26 окт 2005, 13:38

Сообщение cympak »

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

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

Что-то как-то не тянет на докторскую...
...а на каком основании ограниченность некоторых делать законом для всех?

Аватара пользователя
myst
Маньяк
Сообщения: 190
Зарегистрирован: 04 окт 2005, 15:46
Откуда: не возвращаются

Сообщение myst »

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

michael
Неотъемлемая часть форума
Сообщения: 434
Зарегистрирован: 12 апр 2004, 11:00
Откуда: г. Владивосток
Контактная информация:

Сообщение michael »

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

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

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

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

Аватара пользователя
myst
Маньяк
Сообщения: 190
Зарегистрирован: 04 окт 2005, 15:46
Откуда: не возвращаются

Сообщение myst »

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

2. :D Хочешь и на ёлку залезть и руки не ободрать? Не получится.
Иными вечерами я пью, чтобы кого-нибудь не пристрелить. Это акт благотворительности. Не за что.

Аватара пользователя
cympak
Увлекающийся
Сообщения: 114
Зарегистрирован: 26 окт 2005, 13:38

Сообщение cympak »

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

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

Gnida
Неотъемлемая часть форума
Сообщения: 346
Зарегистрирован: 04 апр 2004, 22:38

Сообщение Gnida »

С опытом ошибки не изчезают , а умнеют

michael
Неотъемлемая часть форума
Сообщения: 434
Зарегистрирован: 12 апр 2004, 11:00
Откуда: г. Владивосток
Контактная информация:

Сообщение michael »

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

Аватара пользователя
myst
Маньяк
Сообщения: 190
Зарегистрирован: 04 окт 2005, 15:46
Откуда: не возвращаются

Сообщение myst »

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

michael
Неотъемлемая часть форума
Сообщения: 434
Зарегистрирован: 12 апр 2004, 11:00
Откуда: г. Владивосток
Контактная информация:

Сообщение michael »

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

Ответить