Comments 28
Ох жесть… Я дочитал)
Это конечно очень круто, что можно на этапе компиляции что-то сложное вычислять, но мне все-же проще посчитать на калькуляторе за 10 секунд, чем неделю писать и как-то отлаживать такую вот штуковину.
Это конечно очень круто, что можно на этапе компиляции что-то сложное вычислять, но мне все-же проще посчитать на калькуляторе за 10 секунд, чем неделю писать и как-то отлаживать такую вот штуковину.
+2
Это конечно очень круто, что можно на этапе компиляции что-то сложное вычислять, но мне все-же проще посчитать на калькуляторе за 10 секунд
Вы проглядели последний тэг :)
как-то отлаживать такую вот штуковину.
Боюсь это невозможно. Делается же все в compile-time.
Вы проглядели последний тэг :)
как-то отлаживать такую вот штуковину.
Боюсь это невозможно. Делается же все в compile-time.
+3
вообще сложно что-то отлаживать на шаблонах в C++
+4
Интересное продолжение!
> Для хранения чисел с плавающей точкой будем использовать соотношение двух целых чисел — дробь.
Не-а. Плавающая точка это представление чисел в виде мантиссы и порядка. У вас получилась арифметика рациональных чисел, пусть и неточная.
Единственное что могу добавить: для сокращения лучше бы искать НОД. Или слишком долго компилируется?
> Для хранения чисел с плавающей точкой будем использовать соотношение двух целых чисел — дробь.
Не-а. Плавающая точка это представление чисел в виде мантиссы и порядка. У вас получилась арифметика рациональных чисел, пусть и неточная.
Единственное что могу добавить: для сокращения лучше бы искать НОД. Или слишком долго компилируется?
+2
>Интересное продолжение!
Спасибо :)
>для сокращения лучше бы искать НОД. Или слишком долго компилируется?
После неточного сокращения (reduce_inaccurate) делается попытка снова сократить точно, то есть снова бы пришлось искать НОД, поэтому я сразу отказался от этого. Простые числа до 100 считаются же всего 1 раз.
Спасибо :)
>для сокращения лучше бы искать НОД. Или слишком долго компилируется?
После неточного сокращения (reduce_inaccurate) делается попытка снова сократить точно, то есть снова бы пришлось искать НОД, поэтому я сразу отказался от этого. Простые числа до 100 считаются же всего 1 раз.
0
Простые числа — да, один раз. Но перебор и попытки разделить нацело выполняются каждый раз. Так как максимальное количество шагов в алгоритме Эвклида будет меньше сотни для 64-разрядных чисел и pi(100)=25, разница в производительности должна быть не очень большой, а выигрыш в точности получить можно.
0
Я написал сокращение через НОД, если интересно вот, то что изменилось:
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/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 не изменилась.
+1
А если реализовать через остаток от деления (алгоритм Эвклида, а не двоичный алгоритм Эвклида): pastebin.com/H9TvWdeW
На g++ 4.6.1 без НОД sqrt(10000): real 0m1.359s
С НОД: real 0m0.358s
На g++ 4.6.1 без НОД sqrt(10000): real 0m1.359s
С НОД: real 0m0.358s
+1
А что, НОД так долго ищется? Там же оценка сверху на количество шагов Log_2(n+m), если я правильно помню. Что для 64-битных чисел дает 65 шагов.
+1
Месье знает толк, ага. Идея Александреску живут и побеждает!
+2
Стоит заметить что пользователи GCC >=4.5 могут вместо всего вышеприведённого написать constexpr-функцию (часть стандарта C++0x) и в ней спокойно работать с желаемым типом данных, будь то структура или число с плавающей точкой.
+10
Есть библиотека в бусте boost::rational. Зарелизили в 1.47 (последней). Делает то же.
0
just for fun вещь конечно. но как упоминалось выше мисье знает толк в извращениях
0
Увидел пару интересных приёмов кунг-фу (например определение числа цифр в числе на этапе компиляции = sizeof(#n)-1 ). В общем, спасибо!
0
Кстати, очень аккуратный и изящный код. А извращенцем зовут ниасиляторы! :P
+1
основной алгоритм:С какой целью выбирается наименьшее значение?
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)
}
+1
Я поясню свой вопрос: выбирая наименьшее значение из текущего и следующего приближений, в случае если вы выбираете начальное приближение < sqrt(x), алгоритм вернёт его же после произвольного числа итераций.
0
Хорошая разминка для мозга, в принципе все элементарно. Вот когда я решил написать свою библиотеку compile-time для работы со списками, векторами данных, для работы со строками во время компиляции, чуть мозг себе не сломал.
0
boost::ratio же, не?
А на практике удобнее boost::rational — он не на этапе компиляции, но зато имеет меньшее число ограничений.
А на практике удобнее boost::rational — он не на этапе компиляции, но зато имеет меньшее число ограничений.
0
Only those users with full accounts are able to leave comments. Log in, please.
Вычисления с плавающей точкой на этапе компиляции