Цитата

Согласно алгоритма умножаются только последние цифры, значит если число делится на 5,25, 125 ..., то оно оканчивается на пять, соответсвенно я множу на 5 и делю на 10 (итого делю на 2)

до меня это дошло сегодня по дороге на работу

Цитата

Дополнительно, чтобы от этой процедуры не потерять значимость, т.к. зависимость при умножении на пять существует от предыдущей цифры числа

да вроде бы не зависит
дело в том, что после умножения на 5 в конце должно остаться четная цифра, так что последней цифры достаточно для умножения

Олег, ты хош сказать, что перед пятёркой ты не обрезаешь. Ну допустим, когда у нас будет число кратное пяти то мы будем делить на два не однозначное а двузначное. Только это всё фигня. Когда ты залезешь до n=400000 (например), то тебе придётся делить на 128 и от твоего двузначного останется только нафиг никому не нужный нолик.
Добавлено @ 11:59
Может я совсем тупой?????

Просто когда мы умножаем на каждое пятое число количество нулей в факториале увеличивается как минимум на 1. Когда множим на каждое 25-ое - на 2. На каждое 125 - на 3. И т. д.

Короче, по-моему, алгоритм Олега работать не будет. Проще реализовать, проверить на 400000 и сравнить с результатами других алгоритмов.




maxim1000

Теперь что касается моей проги.
Короче, я решил выяснить закономерность этих самых последних чисел. И напихал их в файл много много, начиная от n=0. Получил примерно следующее:
1126422428886828868244846448468868222428…
Начал разбираться и выяснил, что весь этот файл состоит из четырёх пятёрок:
22428
44846
88682
66264
(кроме первой пятерки, т. к. там две первых единицы).
Потом решил выяснить как располагаются эти пятёрки и сляпал файл с первыми цифрами этих пятёрок, т. е. выдиарл каждое пятое число. Там тоже получились четыре разных последовательности из пяти цифр. Потом выдирал каждое 25-ое, 125 и там тоже было по четыре последовательности из пяти цифр и в каждом случае своя. Когда я выдрал каждое 625-ое там тоже получилась последовательность и она была точь в точь как в самом первом варианте. В 3125-ых как во втором. В общем я наляпал до 5^7 и чисто интуитивно решил, что дальше тоже зациклится (хотя фактически, хрен его знает). Вот на этом принципе прога и написана.

Цитата

Олег, ты хош сказать, что перед пятёркой ты не обрезаешь. Ну допустим, когда у нас будет число кратное пяти то мы будем делить на два не однозначное а двузначное.

насколько я понял, не предполагается вообще хранить что-то кроме последней цифры
я тут даже набросал программку

Код

int func2(unsigned int n) {  unsigned int x,c;  x=1;  for(c=1;c<=n;c++)  {    int qqq=c;    while(qqq%5==0)    {      qqq/=5;      x/=2;      if(x%2)        x+=5;    }    x*=(qqq%10);    x%=10;  }  return x; }

умножение на 5 здесь действительно заменено на деление на 2
только при делении на два обычного числа последней цифры недостаточно (например, ***2/2 может быть ***1 или ***6)
но если делить не обычное число, а факториал, в котором просто-таки куча множителей 2, то мы знаем, что последняя цифра четная, поэтому вполне достаточно хранить только одну последнюю цифру...

кстати, мне кажется, что с помощью такого подхода можно доказать ту закономерность, котору ты выявил экспериментально

maxim1000, но ты заметь, закономерность... хитрая, короче. Не просто цикл какой-то.
Добавлено @ 16:44
Кстати, я надеюсь, в целом алгоритм понятен (без деталей)...

хитрая закономерность или нет, зависит от того, как на нее смотреть
то, что используются куски по 5 тоже закономерно
дело в том, что периодичность последней цифры - 10
т.к. x и x+5 совершенно одинаково влияют на результат, то периодичность и получается 5
а куски совсем не странные:
например 22428:
2*1=2
2*2=4
4*3=2 (последняя цифра)
2*4=8
аналогично для остальных кусков (которые просто отличаются начальной цифрой)
когда среди множителей встречается 5, происходит деление, что обеспечивает "сложную" закономерность появления кусков

maxim1000. Нет, ну это-то понятно. Просто ты сказал:

Цитата

кстати, мне кажется, что с помощью такого подхода можно доказать ту закономерность, котору ты выявил экспериментально

А я сказал:

Цитата

хитрая, короче. Не просто цикл какой-то.

имея в виду, что за этим доказательством придётся посидеть.

Кстати, у меня возникла мысль о том, что может быть получится найти не только последнюю цифру, но и предпоследнюю и перед ней..... Как ты думаешь, maxim1000, может такое получиться? Просто законы по которым вываливается последняя, предпоследняя и все за ними могут быть похожи друг на друга и таким образом можно будет сляпать алгоритм нахождения любого факториала за достаточно короткое время. Только проблемка будет - как определить количество разрядов числа у n!. А ещё я подумал, что, возможно, такой алгоритм уже давно придуман и можно особо не пыжиться......

Вот.

Цитата(EKoshelev @ 1.12.2004, 08:35)

Кстати, у меня возникла мысль о том, что может быть получится найти не только последнюю цифру, но и предпоследнюю и перед ней..... Как ты думаешь, maxim1000, может такое получиться?

думаю, можно: все операци делать по остатку от деления не на 10, а на 100
единственная сложность: умножение на 5 (т.е. деление на 2)
но, думаю, и она решаема: при делении на два я использовал то, что последняя цифра должна быть четной, в этом случае, наверное, нужно будет использовать кратность какому-нибудь большему числу...

Цитата

Просто законы по которым вываливается последняя, предпоследняя и все за ними могут быть похожи друг на друга и таким образом можно будет сляпать алгоритм нахождения любого факториала за достаточно короткое время.

сомнительно, хотя... кто его знает...

Цитата

Только проблемка будет - как определить количество разрядов числа у n!.

можно взять десятичный логарифм всех чисел и сложить
точности, может быть недостаточно, но можно округлить в бОльшую сторону...

Цитата(EKoshelev @ 30.11.2004, 11:49)

Олег, ты хош сказать, что перед пятёркой ты не обрезаешь. Ну допустим, когда у нас будет число кратное пяти то мы будем делить на два не однозначное а двузначное. Только это всё фигня. Когда ты залезешь до n=400000 (например), то тебе придётся делить на 128 и от твоего двузначного останется только нафиг никому не нужный нолик.

Повторю еще раз, я ДОКАЗАЛ правильность своего алгоритма в первом сообщении.
Там же однозначно доказано, что при умножении на пять ЕСТЬ зависимость от предыдущей цифры.
Все эти высказавания основываются на формулах, которых я давал.

Итого, в связи с тем, что я работаю с цифрами, то при любом числе , даже при СЕПТИЛИОНЕ , последняя цифра - это число от 0 до 9 и делить мне придется всегда только на 2, даже не на 4, не говоря о 128

Цитата

Там же однозначно доказано, что при умножении на пять ЕСТЬ зависимость от предыдущей цифры.

если делить делить на 2 любое число - несомненно зависит
если рассматривать такое специфическое число, как факториал - нет
используется то, что последняя ненулевая цифра всегда четная - тогда можно обойтись без знания предпоследней...

ovr2000

Цитата

(k*10+2*i)*(p*10+5)=k*p*100+10*(p*2*i+5*k)+2*5*k

Когда я учился в школе у нас за такое двойки ставили (надеюсь ошибку сам найдёшь). Это первое. Второе. Я чё-то не нашёл в твоём великом и могучем алгоритме никакой аналогии с твоим не менее великим доказательством.

Третье:

Цитата

p*n+6*k

(или какую бы ты там мудрую формулу не выдумал). Предположим:
p = 2
n = 2
k = 1
чему будет равно количество десяктов???

А если результат подогнать побольше (например, до 1000), то твоя последняя цифра таковой уже являться не будет.

Догнал??? или нет ещё. Если нет, попробуй вписать на вход своей проги 400000 и посмотри что она выдаст.

Это сообщение отредактировал(а) EKoshelev - 3.12.2004, 15:56

ovr2000, короче я с 400000 погорячился. Вот те факториал 25:

25! = 15511210043330985984000000

А теперь на своей проге посчитай.

Верно , р - то есть вторая цифра множителя влияет на результат
мой алгоритм не верен, додумаю

Извините, но пятерки накапливаются
Алгоритм нужно менять кардинально, т.к. зависимость при умножении на 5 затрагивает не только 2-е но и более высокие порядки числа.
Нужно не перемножать пятерки а складировать, вместе с четными числами

Это сообщение отредактировал(а) ovr2000 - 4.12.2004, 11:44

ovr2000, ну вот, блин, я же говорил - не то.


maxim1000

Цитата

Цитата Только проблемка будет - как определить количество разрядов числа у n!. можно взять десятичный логарифм всех чисел и сложить точности, может быть недостаточно, но можно округлить в бОльшую сторону...

Я вот подумал что получится, если десятку потом возвести в степень, равную сумме этих логарифмов? Интересно, много времени будет жрать эта процедура? Можно ещё будет натуральные логарифмы использовать, чтобы по быстрее было. Я вот только забыл как логарифм в числовой ряд раскладывать, зато помню, что при вычислении экспоненты нужны факториалы.

Попробовал тут выяснять закономерность предпоследних чисел. Там тоже наборы из пяти цифр, только их значительно больше. Сколько точно ещё не выяснил, но где-то около ста...

Цитата

Я вот подумал что получится, если десятку потом возвести в степень, равную сумме этих логарифмов?

в обычных числах не получится (результат туда не поместится)

Цитата

Можно ещё будет натуральные логарифмы использовать, чтобы по быстрее было

это практически никакого ускорения не даст
log x=ln x/ln 10
а операция деления занимает пренебрежимо малое время по сравнению с вычислением логарифма