Тут есть хоть один толковый программист????

← →
вразлет © (2005-12-28 12:47) [40]

Витёк

А что платишь?

← →
Витёк (2005-12-28 12:54) [41]

The_scorpion, спасибо!

← →
ferr © (2005-12-28 12:56) [42]

The_scorpion © (28.12.05 11:31) [32]

1 байт под одно число по меньшей мере не выгодно, а ещё и медленно.

использовать строки тоже не гуд, они должны быть константными) © C#

← →
The_scorpion © (2005-12-28 13:05) [43]

1 байт под одно число по меньшей мере не выгодно, а ещё и медленно.
Это выгодно в плане простоты и понимания, по скорости проигрыша нет, в памяти проигрыша тоже нет(256 байт это ОЧЕНЬ мало).
ИМХО: Алгоритм очень хорош

← →
ferr © (2005-12-28 13:09) [44]

The_scorpion © (28.12.05 13:05) [43]
1) log(10,2) / 8 ~= 41 %.
2) быстрее всего процессор работает с машинным словом.

← →
The_scorpion © (2005-12-28 13:09) [45]

> Спасибо за развернутый ответ. Вы говорили о ТП или все-таки
> о Дельфи? Чем вам те же динамические массивы не угодили?
> Например.

Можно и с ними...но со стрингами красивее будет...
ИМХО: Дело вкуса..:)))

← →
The_scorpion © (2005-12-28 13:12) [46]

> 1) log(10,2) / 8 ~= 41 %.

а это ты откуда взял?

> 2) быстрее всего процессор работает с машинным словом.

Ты думаешь много времени уйдет на изменение регистра кода на единицу?
К разрядам быстрее доступ будет

← →
Kerk © (2005-12-28 13:14) [47]

The_scorpion © (28.12.05 13:12) [46]
> 1) log(10,2) / 8 ~= 41 %.

а это ты откуда взял?

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

← →
ferr © (2005-12-28 13:15) [48]

> а это ты откуда взял?

1 байтом код-ся 10 различных значений

← →
palva © (2005-12-28 13:24) [49]

Если нужен результат...
use Math::BigInt; $x = Math::BigInt->new(1); for($i=1; $i<=100; $i++) { $x = $x->bmul($i); } print $x; 93326215443944152681699238856266700490715968264381 62146859296389521759999322991560894146397615651828 62536979208272237582511852109168640000000000000000 00000000

← →
The_scorpion © (2005-12-28 13:33) [50]

> Ну как бы неплохо мат.часть почитывать прежде чем на олимпиады
> ходить.
> Хотя, если ограничений по времени нет, то твой код сойдет.
>

Так почитываю, иногда...:)))не понимаю откуда вы взяли это число 10,2...
Еще раз повторюсь, проигрыша по времени не будет. Советую почитывать ассемблер...:)))

> 1 байтом код-ся 10 различных значений

Это плохо?

← →
ferr © (2005-12-28 13:36) [51]

> не понимаю откуда вы взяли это число 10,2...

забавно. ln(10)/ln(2).

> Это плохо?

это 41%

← →
Kerk © (2005-12-28 13:38) [52]

The_scorpion © (28.12.05 13:33) [50]
Еще раз повторюсь, проигрыша по времени не будет.

Будет.

← →
Думкин © (2005-12-28 13:39) [53]

> The_scorpion © (28.12.05 13:33) [50]

2 isn"t fractional part but it"s a base of log.

← →
The_scorpion © (2005-12-28 13:39) [54]

> Kerk © (28.12.05 13:14) [47]

Предлагаю вам написать этот алгоритм своим способом и мы сравним их по трем параметром:1) читабельность кода 2) скорость работы 3) затрачиваемые ресурсы.
ИМХО: не люблю оторванных от реальности теоретиков...:)))

← →
The_scorpion © (2005-12-28 13:40) [55]

> ferr ©

Вам тоже...:)))

← →
Kerk © (2005-12-28 13:41) [56]

The_scorpion © (28.12.05 13:39) [54]
Предлагаю вам написать этот алгоритм своим способом и мы сравним их по трем параметром

Мой код в [31]. Не самый оптимальный, но лучше твоего. Только ты сравнивай на больших числах. 100 разрядов - не серьезно.

> не люблю оторванных от реальности теоретиков...:)))

Это ты мне? LOL

← →
The_scorpion © (2005-12-28 13:44) [57]

Давай на больших... выкладывай, оценим...:)))

← →
Kerk © (2005-12-28 13:47) [58]

123^7890 = [16490 десятичных знаков]
потрачено 265 мс

← →
palva © (2005-12-28 13:56) [59]

123^7890 на перле 25 сек (700 Мгц)

← →
The_scorpion © (2005-12-28 14:05) [60]

1000 операции сложения в каждой около 200 разрядах на моем Celeron 2,4 ггц получаем : Мой Алгоритм 266 мс , ваш чуть меньше 1 сек, комментарии излишни.
ИМХО тему можно закрыть.

← →
Kerk © (2005-12-28 14:09) [61]

The_scorpion © (28.12.05 14:05) [60]
1000 операции сложения в каждой около 200 разрядах на моем Celeron 2,4 ггц получаем : Мой Алгоритм 266 мс , ваш чуть меньше 1 сек, комментарии излишни.

В [58] и [59] указаны конкретные числа и результаты. У тебя что-то все "около". К чему бы это... :))

← →
Kerk © (2005-12-28 14:11) [62]

Тестовый пример 123^7890
Реализовал бы быстренько умножение через свое сложение, а затем и возведение в степень. Оно ведь не долго.

← →
The_scorpion © (2005-12-28 14:18) [63]

> Тестовый пример 123^7890
> Реализовал бы быстренько умножение через свое сложение,
> а затем и возведение в степень. Оно ведь не долго.

Реализую вечеро, а то зачет горит...:)))

> В [58] и [59] указаны конкретные числа и результаты. У тебя
> что-то все "около". К чему бы это... :))

К тому, что я умею ПРАВИЛЬНО тестировать...и использовал random, а его сложно предсказать(хотя и возможно).
ИМХО: если ваш алгорит слабее по скорости, то надо это просто признать, это было бы красивее и честнее.

← →
ferr © (2005-12-28 14:24) [64]

чего стоит хотя бы вот эта строчка

for i:=1 to dlin-dlin2 do str:="0"+str;

← →
Kerk © (2005-12-28 14:28) [65]

ferr © (28.12.05 14:24) [64]

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

← →
ferr © (2005-12-28 14:41) [66]

вот вам и тест:

program Project2; {$APPTYPE CONSOLE} uses Windows; const Max = 100000; var str1, str2 : string; var i1,i2 : int64; i : integer; begin QueryPerformanceCounter(i1); for i:=1 to Max do str1:="0"+str1; QueryPerformanceCounter(i2); writeln(i2-i1); QueryPerformanceCounter(i1); SetLength(str2, Max); for i:=1 to Max do str2[i]:="0"; QueryPerformanceCounter(i2); writeln(i2-i1); readln; end.

← →
Sha © (2005-12-28 15:56) [67]

> The_scorpion ©
> Kerk ©

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

← →
Kerk © (2005-12-28 17:03) [68]

Sha © (28.12.05 15:56) [67]

Согласен. Честно говоря, мне тогда было просто лень это реализовывать. :)

> чего стоит хотя бы вот эта строчка
>
> for i:=1 to dlin-dlin2 do
> str:="0"+str;

Что вам не нравится?

> Sha © (28.12.05 15:56) [67]

А кто спорит?
Только перевод из десятичные в двоичную займет еще минут 20-30, на олимпиадах это смертельное время.

> Что вам не нравится?

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

> The_scorpion © (28.12.05 19:10) [69]
> перевод из десятичные в двоичную займет еще минут 20-30,
> на олимпиадах это смертельное время

А где написано, что ответ должен быть в десятичной системе?
Для больших чисел это обычно не требуется :)

Вот тебе "олимпиадный" вариант:

function MulString(const t, s: string): string; var i, j, j1, j2, lent, lens, len, sum: integer; begin; lent:=Length(t); lens:=Length(s); len:=lent+lens; SetLength(Result,len); sum:=0; for i:=1 to len do begin; j1:=i+1-lens; if j1<=0 then j1:=1; j2:=i; if j2>lent then j2:=lent; for j:=j1 to j2 do sum:=sum+(ord(t[j])-ord("0"))*(ord(s[i+1-j])-ord("0")); Result[i]:=chr(sum mod 10 + ord("0")); sum:=sum div 10; end; while (len>1) and (Result[len]="0") do dec(len); SetLength(Result,len); end; procedure DecString(var s: string); var i: integer; begin; for i:=1 to Length(s) do begin; if s[i]>"0" then begin; if (s[i]="1") and (i>1) and (i=Length(s)) then SetLength(s,i-1) else dec(s[i]); break; end; s[i]:="9"; end; end; function Factorial(n: cardinal): string; var s: string; begin; s:=ReverseString(IntToStr(n)); Result:="1"; while (s[1]<>"0") or (Length(s)>1) do begin; Result:=MulString(Result,s); DecString(s); end; Result:=ReverseString(Result); end;

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

Хорошо:
dlin:=dlin-dlin2;
for i:=1 to dlin do
теперь все ok

> А где написано, что ответ должен быть в десятичной системе?
>
> Для больших чисел это обычно не требуется :)

А кому нужны двоичные числа? Их только программисты и понимают...

> The_scorpion © (28.12.05 20:22) [72]
> А кому нужны двоичные числа? Их только программисты и понимают...

Есть еще кое-кто. Вернее, кое-что. Вот ему они и нужны в первую очередь.

Для справки. Число 100! записывается при помощи 159 десятичных знаков.
Не уверен, что ты его сможешь прочесть :)
А уж понять...

> Для справки. Число 100! записывается при помощи 159 десятичных
> знаков.
> Не уверен, что ты его сможешь прочесть :)
> А уж понять...

... поэтому выводы о правильности работы конкурсной программы будут составляться случайным образом :-))

> [49] palva © (28.12.05 13:24)
> Если нужен результат...
>
> use Math::BigInt;
> $x = Math::BigInt->new(1);
> for($i=1; $i<=100; $i++) {
> $x = $x->bmul($i);
> }
> print $x;

тоже самое на питоне :)
result = 1L for i in range (1L,100L): result = result*i; print result

на php
$s = "1";
for ($i=1;$i<=10000;$i++)
$s=bcmul($s, $i);
echo "(".strlen($s).") ".$s;

10000! составляет 35660 знаков :)

> Не уверен, что ты его сможешь прочесть :)
> А уж понять...

Мои возможности в понимание всего непонятного очень высоки...:)))

> Kerk © (29.12.05 00:09) [74]
> The_scorpion © (28.12.05 20:22) [72]
> теперь все ok
>
> Нет

БУ..:))))))))))))))))

> Вот тебе "олимпиадный" вариант:

На олимпиадах понятие о процедурном и модульном программирование практически отсутствует...

Все ясно. Очередной пионер. А начинал неплохо.

Тут есть хоть один толковый программист???? Найти похожие ветки