Нашли или выдавили из себя код, который нельзя назвать нормальным, на который без улыбки не взглянешь? Не торопитесь его удалять или рефакторить, — запостите его на говнокод.ру, посмеёмся вместе!
+131
#include <stdio.h>
void factorization(int num, int show) {
int num1 = num;
int n = 2;
while ( n*n <= num1 ) {
if ( num%n == 0 ) {
num = num / n;
if ( show )
printf( "%d\n", n );
} else {
n ++;
}
}
}
int main() {
int i = 0;
while ( i < 1000 ) {
factorization(999999, 0);
i ++;
}
return 0;
}
Опубликовано в одной из ссылок с http://habrahabr.ru/blogs/ruby/48952/ (если надо, точную ссылку найду позже).
Код раскладывает число на простые множители тупым перебором делителей. Мало того, что этот код медленный, так он иногда последний множитель пропускает. Одновременно и ошибка, и скорость исправляются так:
- while ( n*n <= num1 ) {
+ while ( n <= num ) {
Неожиданно, правда?
Запостил: 
inkanus-gray,
13 Июля 2010
Follow us!
Ну ладно, пусть детишки дальше в игрушки играются
К тому же микроконтроллер это всё таки не большой адронный коллайдер.
Так что имеет место быть.
>>>>while ( n*n <= num1 ) {
>>>>+ while ( n <= num ) {
Ыыы)))
да что вы тут такое пишете - вы походу вообще не в теме
1. перебирать надо до (корня от n)+1 - вычисленного 1 раз (квадратичный спид-ап) именно для этого там n*n, но зачем каждый раз умножать если можно взять корень от num1
2. перебирать надо нечетные со степом 2 - спид-ап в два раза от пункта 1,
проверив предварительно двойку
3. если хотим большего надо пользовать формулу 6k+1, 6*k-1 - спидап в полтора раза от пункта 2.
это самое примитивное, если найду запостю труЪ алгоритм, короче самое быстрое что мне удавалось писать раскладывало числа до 2^64 менее чем за секунду кажись.
правда это был асм, FPU, SSE и еще пару хитрых оптимизаций
вообще если кому надо математическое обоснование - пишите.
ЗЫ в пункте 3 надо сначало проверить 2 и 3 а потом юзать формулу 6k+1, 6*k-1
несложно сделать из этого факторизацию, даже рекурсивный способ должен работать быстрее вышеприведенных
if ( num%2 == 0 ) return 2;
if ( num%3 == 0 ) return 3;
int root=((int) sqrt(num))+1;
int k=(root/6)+1;
for (int i=1,div=0;i<k;i++){
div+=6;
if ( num%(div-1) == 0 ) return (div-1);
if ( num%(div+1) == 0 ) return (div+1);
}
//число простое
return -1;
Про корень от num1 я тоже думал, но с ним получается медленнее. Надо будет выяснить, почему.
Кто-нибудь заметил, что в предложенном патче num вместо num1? Цикл автоматически остановится на последнем множителе.
Pro et contra
Pro: в данном примере последняя итерация будет, когда n == num == 37 вместо n == sqrt(num1) == 999.
Contra: для чисел вида 2*x, 3*x, 5*x, где x — простой множитель, намного больший, чем sqrt(num1), будет медленно.
Резюме: использовать комбинированное условие для завершения.
ибо корень первая и наиглавнейшая оптимизация
нет, 30*n и исключение 5 - точно быстрее, дальше - зависит от того какие простые числа,
если маленькие - увеличивается размер кода, и он не влазит в L1 - что снижает скорость
если большие - там можно цикл намутить и бренчинг кроется выигрышем в пропусках чисел кратных 7 и 11
но тут надо генить таблицу.
30*n - весьма оптимальное и простое сочетание
>>>>Про корень от num1 я тоже думал, но с ним получается медленнее.
никак нет, выигрыш в скорости - просто нереальный (квадратичный), попробуй то что я набросал на числах около 100 миллионов.
пример так надо перебирать до миллиона - n
а так до тысячи - корень из n
но ВАЖНО корень он не для факторизации - он для проверки на простоту (или поиска первого делителя)
тут для разных диапазонов чисел разные оптимальные алгоритмы ))))
но т.к. в те времена когда я этим занимался она не влазила в мои 512Мб, пришлось делать хитрые вещи - типа этих 6*n и 30*n, а хранить числа либо как массив битов простое - не простое (причем хранились только значения для n) (и массив битов - на самом деле был байтовым)
либо как разницу между простыми числами, деленную пополам т.к. она почти всегда была меньше байта, то одно простое число занимало байт.
+ у меня был массив исключений для разниц, которые были больше 512 (напоминаю я делю разницу пополам, поскольку она всегда четная)
то есть я получал биты через инлайн-спец-функцию меняющую бит адресацию на байт и извлекающую их из байтового массива
а мы х - будем проверять на простоту тоже по корню )))) если простое - напечатали и вышли, нет - нашли множитель итд..
я же сказал рекурсивно, но я делал и без рекурсии