Как стать автором
Обновить

Комментарии 28

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

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

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

>для сокращения лучше бы искать НОД. Или слишком долго компилируется?
После неточного сокращения (reduce_inaccurate) делается попытка снова сократить точно, то есть снова бы пришлось искать НОД, поэтому я сразу отказался от этого. Простые числа до 100 считаются же всего 1 раз.
Простые числа — да, один раз. Но перебор и попытки разделить нацело выполняются каждый раз. Так как максимальное количество шагов в алгоритме Эвклида будет меньше сотни для 64-разрядных чисел и pi(100)=25, разница в производительности должна быть не очень большой, а выигрыш в точности получить можно.
Я написал сокращение через НОД, если интересно вот, то что изменилось:
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 не изменилась.
А если реализовать через остаток от деления (алгоритм Эвклида, а не двоичный алгоритм Эвклида): pastebin.com/H9TvWdeW

На g++ 4.6.1 без НОД sqrt(10000): real 0m1.359s
С НОД: real 0m0.358s
здорово, обновил библиотеку
While you are at it, NOD -> GCD (greatest common divisor).
А что, НОД так долго ищется? Там же оценка сверху на количество шагов Log_2(n+m), если я правильно помню. Что для 64-битных чисел дает 65 шагов.
Месье знает толк, ага. Идея Александреску живут и побеждает!
Стоит заметить что пользователи GCC >=4.5 могут вместо всего вышеприведённого написать constexpr-функцию (часть стандарта C++0x) и в ней спокойно работать с желаемым типом данных, будь то структура или число с плавающей точкой.
Есть библиотека в бусте boost::rational. Зарелизили в 1.47 (последней). Делает то же.
названия совпадают, но boost::rational это совершенно другое,
и появилась она не в 1.47, в 1.31 уже точно была
Спасибо за информацию, запомню.
just for fun вещь конечно. но как упоминалось выше мисье знает толк в извращениях
Увидел пару интересных приёмов кунг-фу (например определение числа цифр в числе на этапе компиляции = sizeof(#n)-1 ). В общем, спасибо!
Кстати, очень аккуратный и изящный код. А извращенцем зовут ниасиляторы! :P
основной алгоритм:
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)
}
С какой целью выбирается наименьшее значение?
согласен, он не нужен, спасибо
переписал с алгоритма для нахождения корня в целых числах,
а там, чтобы обеспечить sqrt(x)*sqrt(x) =< x
Прошу прощения, смотрите комментарий ниже.
Я поясню свой вопрос: выбирая наименьшее значение из текущего и следующего приближений, в случае если вы выбираете начальное приближение < sqrt(x), алгоритм вернёт его же после произвольного числа итераций.
Хорошая разминка для мозга, в принципе все элементарно. Вот когда я решил написать свою библиотеку compile-time для работы со списками, векторами данных, для работы со строками во время компиляции, чуть мозг себе не сломал.
boost::ratio же, не?
А на практике удобнее boost::rational — он не на этапе компиляции, но зато имеет меньшее число ограничений.
boost::ratio это то, что нужно, спасибо.
К своему оправданию могу сказать, что boost::ratio вышла в последней версии 1.47, я использовал 1.46 :(
Комментатор выше, который говорил про boost::rational, скорее всего имел именно boost::ratio.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории