Comments 17
В подобных упражнениях намного важне и сложнее написать правильный бенчмарк, чем собственно сам код, который меряет что-либо.
Современные компиляторы очень сложны в своих оптимизациях, при этом могут случаться парадоксальные на первый взгляд вещи, когда -o2 работает медленнее -o1 и тому подобные чудеса с -o3/-oX. И это только в рамках одной версии gcc.
Тем более глубокой становится кроличья нора, если захотеть мерять разные платформы с архитектурами под одну гребёнку.
Всякие прогревы кэшей и т.п. можно уже и не вспоминать.
Ну тут есть ряд стандартных приёмов. Излишняя оптимизация на работе с некоторыми переменными устраняется установкой volatile на них. Влияние прогрева кэша данных лечится мерами типа: массив на миллион входных значений преобразуется в цикле в массив в миллион выходных строк; кода — выполнить на каждой итерации ещё какое-то действие (толстое, но стороннее). И так далее.
Против хитрых эффектов оптимизаций — надо приводить результаты за все базовые уровни. Ну и заглянуть таки в ассемблерник, проверить, нет ни там неожиданных безумий.
А потом — мерять и мерять :)
Там несколько другая задача, так как считаются остатки не обязательно по модулю простого числа, но кроме практических задач есть еще и научные, и для решения некоторых задач приходится перебирать большие диапазоны чисел, поэтому
>что изменится, если Вы будете считать остатки в 10 раз медленнее или в 10 раз быстрее?
от этого может зависить, напишете вы научную статью через месяц или через год!
Если Вы имеете в виду Number theoretic transform
Ну да, именно его и имел в ввиду. Там было простое число 2^2^4+1 = 65537 на которое удобно умножать ((x<<16)+x).
это самый быстрый способ перемножить два многочлена с целыми коэффициентами или два целых числа произвольной разрядности
Насколько я знаю, на базе свертки с помощью обычного, комплексного FFT, все таки быстрее.
напишете вы научную статью через месяц или через год!
Хм… Будет время подумать?
uint32_t parse_32(char *str)
{
uint32_t a;
memcpy( &a, str, 4);
a = (a & 0x0F0F0F0F) * 2561 >> 8;
a = (a & 0x00FF00FF) * 6553601 >> 16;
return a;
}UPD: А не работает ж, как надо. Но в целом, идея этого метода, она позаимствована из уже существующего алгоритма?
str="9630"
0) a=0x30333639
1) a=0x1E3F60
2) a=0x259E или искомые 9630
str="1876"
0) a=0x36373831
1) a=0x4С5712
2) a=0x754 или искомые 1876
я брал вроде бы отсюда — ссылка, в проекте используется 64битная версия для быстрого парсинга таймстэмпов.
Приключение чисел в ASCII-ландии. Часть 0x01u. Беззнаковые целые числа