Вычисления с плавающей точкой на этапе компиляции

[firexel]

Ох жесть… Я дочитал)
Это конечно очень круто, что можно на этапе компиляции что-то сложное вычислять, но мне все-же проще посчитать на калькуляторе за 10 секунд, чем неделю писать и как-то отлаживать такую вот штуковину.

[dordzhiev]

Это конечно очень круто, что можно на этапе компиляции что-то сложное вычислять, но мне все-же проще посчитать на калькуляторе за 10 секунд
Вы проглядели последний тэг :)
как-то отлаживать такую вот штуковину.
Боюсь это невозможно. Делается же все в compile-time.

[firexel]

Вот и я про то)

[skor]

вообще сложно что-то отлаживать на шаблонах в C++

[gribozavr]

Интересное продолжение!

> Для хранения чисел с плавающей точкой будем использовать соотношение двух целых чисел — дробь.
Не-а. Плавающая точка это представление чисел в виде мантиссы и порядка. У вас получилась арифметика рациональных чисел, пусть и неточная.

Единственное что могу добавить: для сокращения лучше бы искать НОД. Или слишком долго компилируется?

[skor]

>Интересное продолжение!
Спасибо :)

>для сокращения лучше бы искать НОД. Или слишком долго компилируется?
После неточного сокращения (reduce_inaccurate) делается попытка снова сократить точно, то есть снова бы пришлось искать НОД, поэтому я сразу отказался от этого. Простые числа до 100 считаются же всего 1 раз.

[gribozavr]

Простые числа — да, один раз. Но перебор и попытки разделить нацело выполняются каждый раз. Так как максимальное количество шагов в алгоритме Эвклида будет меньше сотни для 64-разрядных чисел и pi(100)=25, разница в производительности должна быть не очень большой, а выигрыш в точности получить можно.

[skor]

Я написал сокращение через НОД, если интересно вот, то что изменилось:
pastebin.com/kRy21zPM

Результаты времени компиляции без НОД для sqrt(1000):

real 0m5.859s
user 0m2.628s
sys 0m0.148s
31.622776825553
-1.41587300855894e-05

С НОД:
real 0m13.373s
user 0m6.540s
sys 0m0.296s
31.622776825553
-1.41587300855894e-05

То есть с НОД дольше (но для меньших чисел алгоритм с НОД выигрывает)
точность -1.41587300855894e-05 не изменилась.

[gribozavr]

А если реализовать через остаток от деления (алгоритм Эвклида, а не двоичный алгоритм Эвклида): pastebin.com/H9TvWdeW

На g++ 4.6.1 без НОД sqrt(10000): real 0m1.359s
С НОД: real 0m0.358s

[skor]

здорово, обновил библиотеку

[gribozavr]

While you are at it, NOD -> GCD (greatest common divisor).

[mihaild]

А что, НОД так долго ищется? Там же оценка сверху на количество шагов Log_2(n+m), если я правильно помню. Что для 64-битных чисел дает 65 шагов.

[skor]

ответил тут

[sgzmd]

Месье знает толк, ага. Идея Александреску живут и побеждает!

[Lockal]

Стоит заметить что пользователи GCC >=4.5 могут вместо всего вышеприведённого написать constexpr-функцию (часть стандарта C++0x) и в ней спокойно работать с желаемым типом данных, будь то структура или число с плавающей точкой.

[Ockonal]

Есть библиотека в бусте boost::rational. Зарелизили в 1.47 (последней). Делает то же.

[skor]

названия совпадают, но boost::rational это совершенно другое,
и появилась она не в 1.47, в 1.31 уже точно была

[Ockonal]

Спасибо за информацию, запомню.

[denim]

just for fun вещь конечно. но как упоминалось выше мисье знает толк в извращениях

[mt_]

Увидел пару интересных приёмов кунг-фу (например определение числа цифр в числе на этапе компиляции = sizeof(#n)-1 ). В общем, спасибо!

[Volfram]

Кстати, очень аккуратный и изящный код. А извращенцем зовут ниасиляторы! :P

[f0rbidik]

основной алгоритм:
sqrt_eval(p, res, x) {
t1 = x/res
t2 = res+t1
tmp = t2/2
less_val = tmp < res? tmp: res
if (p-1 == 0)
return less_val;
return sqrt_eval(p-1, less_val, x)
}

С какой целью выбирается наименьшее значение?

[skor]

согласен, он не нужен, спасибо
переписал с алгоритма для нахождения корня в целых числах,
а там, чтобы обеспечить sqrt(x)*sqrt(x) =< x

[f0rbidik]

Прошу прощения, смотрите комментарий ниже.

[f0rbidik]

Я поясню свой вопрос: выбирая наименьшее значение из текущего и следующего приближений, в случае если вы выбираете начальное приближение < sqrt(x), алгоритм вернёт его же после произвольного числа итераций.

[AxisPod]

Хорошая разминка для мозга, в принципе все элементарно. Вот когда я решил написать свою библиотеку compile-time для работы со списками, векторами данных, для работы со строками во время компиляции, чуть мозг себе не сломал.

[f0b0s]

boost::ratio же, не?
А на практике удобнее boost::rational — он не на этапе компиляции, но зато имеет меньшее число ограничений.

[skor]

boost::ratio это то, что нужно, спасибо.
К своему оправданию могу сказать, что boost::ratio вышла в последней версии 1.47, я использовал 1.46 :(
Комментатор выше, который говорил про boost::rational, скорее всего имел именно boost::ratio.