k нулей - Этюды для программистов

Re[2]: И еще одна программа на C++

	От:	Seon
	Дата:	22.12.08 08:20
	Оценка:

Здравствуйте, Roman Odaisky, Вы писали:

RO>А вот моя версия. Подход немножко другой, используется 10¹⁶-ричная система счисления.

А где же результаты работы?

Степени + временные интервалы?

Меня смутил ретурн вот здесь

                if(has_k_zeros(n[i], k, leftover))
                {
                    std::cout << p << std::endl;
                    return 0;
                }

Re[6]: С++ версии...

	От:	Seon
	Дата:	22.12.08 08:26
	Оценка:

Если что,
у меня есть массиф числа 2^4036332

Re[6]: С++ версии...

	От:	Seon
	Дата:	22.12.08 08:34
	Оценка:

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, Erop, Вы писали:

E>>Вариант с двумя цифрами на байт:
E>>Вариант с четырьмя цифрами на short:
E>>Вариант с четырьмя цифрами на short, и без проверок цепочек нулей, не выходящих на границы цепочек (очевидно, что для k > 2 это не важно)

S>А как на счет 8 на INT?

S>... а еще есть вариант 4 цифры на ИНТ, (по 1 на байт)

E>>Будет время -- попробую обработать переполнение кэша.

S>Есть более радикальное решение:
S>Обрабатывать числа по частям. Ведь для удвоения нам достаточно знать цифру с которой начинать, а это всегда 1, и значение переноса из предыдущего разряда, это 1 или 0 — его запоминать в файле.

S>Расчитываем числа, длиной например в 1 000 000, — это приблизительно 3 200 000-я степень двойки. Продолжаем считать их например до 1000 000 000 000, запоминая в файле для каждой степени один байт, в котором 1 бит — значение переноса, остальные биты — количество нулей, которые имело число с левой стороны. Таким образом получаем файл в 1000 000 байт.

S>Затем мы расчитываем числа со степени 3 200 000, начиная с 1, учитывая значения переноса из файла. А при подсчете нулей, начальное количество нулей берем так же из файла.

S>Ресурс файла по количеству нулей — 127. То есть эта схема файла позволит рассчитать числа до 127 нулей подряд.

S>Этот алгоритм позволит избавить поиск чисел от зависимости на количество используемой памяти программой. И кстати легко может быть распределен между компьютерами.
S>1-й ищет части числа 1 000 000 000 000? второй 1 000 000 000 000, третий 1 000 000 000 000, четвертый 1 000 000 000 000.

S>Кто возьмется писать такую программу, просьба маленькая

:
S>- сделать консольную программу, которая в качестве параметров принимает количество итераций, выходной файл переносов, входной файл переносов. (2 параметра — считать что перенос всегда 0)
S>- программа должна делать периодическое сохранение промежуточных данных (всего массива чисел), для того чтобы в любой момент можно было продолжить вычисления.
S>- должна позволить продолжить вычисления, получив четвертый параметр — текущее состояние

S>

S>Удачи, программисты!

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

Re[14]: k нулей

	От:	Erop
	Дата:	22.12.08 08:44
	Оценка:

Здравствуйте, Seon, Вы писали:

E>>

0:00:01 : 2^242 = 3, 3, len = 73
E>>0:00:01 : 2^377 = 4, 4, len = 114
E>>0:00:01 : 2^1491 = 5, 5, len = 449
E>>0:00:01 : 2^1492 = 6, 6, len = 450
E>>0:00:01 : 2^6801 = 7, 7, len = 2048
E>>0:00:01 : 2^14007 = 8, 8, len = 4217
E>>0:00:09 : 2^100823 = 9, 9, len = 30351
E>>0:04:24 : 2^559940 = 10, 10, len = 168559
E>>0:18:23 : 2^1148303 = 11, 11, len = 345674

Гонял на Core(TM) Duo CPU T2450 2,00 GHz под вистой...
E>>А ты?

S>

Семпрон 1.8 W2003 в belownormal

S>a(12) — 2^4036332 11 часов 18 минут

3:47:15 : 2^4036338 = 12, 12, len = 1215059
3:47:16 : 2^4036339 = 13, 13, len = 1215060

Не совсем понятно от чего 13 не попался сразу. Короче медленно всё. Даже до известного a(17), который пол миллиард, и то бесконечно долго считать будет

S>сейчас приближается к 10 миллионам со скоростью где-то 20 чисел в секунду

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

Re[2]: k нулей

	От:	Erop
	Дата:	22.12.08 08:52
	Оценка:

Здравствуйте, Spiceman, Вы писали:

S>Больше всего понравилось решение на Хаскеле. В одну строчку — впечатлило!
Ну на любом языке с поддержкой длинных чисел будет коротко. Вот на С++ с соответствующей библиотекой, например

Другое дело, что будет медленно.
Кстати, чтобы было веселее, предлагаю немного изменить условие задачи — посчитать функцию a( k, base ), где base -- основание системы счисления.
Конечно для степеней двойки задача вырождается, но можно рассмотреть основание 9 или 11, например...

Re[3]: k нулей

	От:	Seon
	Дата:	22.12.08 08:57
	Оценка:

Здравствуйте, Erop, Вы писали:

E>Конечно для степеней двойки задача вырождается, но можно рассмотреть основание 9 или 11, например...

Не понял, почему вырождается?

Re[2]: И еще одна программа на C++

	От:	Erop
	Дата:	22.12.08 09:00
	Оценка:

Здравствуйте, Roman Odaisky, Вы писали:

RO>А вот моя версия. Подход немножко другой, используется 10¹⁶-ричная система счисления.

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

Кстати, развей мои сомнения про использование std::copy. Ты ошибся или я?

Re[4]: k нулей

	От:	Erop
	Дата:	22.12.08 09:05
	Оценка:

Здравствуйте, Seon, Вы писали:

S>Не понял, почему вырождается?

потому, что "2 в степени 666" в 8-ричной системе записывается как 1 с 222 нулями

Re[3]: k нулей

	От:	Pro100Oleh
	Дата:	22.12.08 09:09
	Оценка:

Здравствуйте, vadimcher, Вы писали:

V>Было бы здорово, если бы все еще свой код выкладывали. Просто интересно сравнить эффективность/простоту для разных языков.

Имхо, суть не в применяемых языках, а в алгоритме. Все приведенные здесь примеры что я пересмотрел (все не смотрел — лень) производят умножения по одной цифре. Я же использую int64 с 17 цифрами, то есть я умножаю в 17 раз быстрее.
Кстати, основная сложность не в умножении, а в проверке числа. Здесь у меня другая оптимизация, но это пока секрет

Pro

Re[10]: И снова об STL

	От:	Roman Odaisky
	Дата:	22.12.08 10:17
	Оценка:	10 (1)

Здравствуйте, Erop, Вы писали:

E>А разве так можно? :shuffle:

Твой код:

    const small* src = buffer + 1;
    small* dst = buffer + 1 + count;
    for( int i = count * 9; i > 0; --i )
        *dst++ = *src++;
    ++*--dst;

и мой код:

std::copy(buffer + 1, buffer + 1 + count * 9, buffer + 1 + count);
++buffer[10 * count];

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

До последнего не верил в пирамиду Лебедева.

Re[3]: И еще одна программа на C++

	От:	Roman Odaisky
	Дата:	22.12.08 10:21
	Оценка:

Здравствуйте, Seon, Вы писали:

S>А где же результаты работы? :))
S>Степени + временные интервалы? :shuffle:

~/src :) time ./kzeros 7
6801
./kzeros 7  0.12s user 0.00s system 100% cpu 0.124 total
~/src :) time ./kzeros 8
...10000...
14007
./kzeros 8  0.46s user 0.01s system 99% cpu 0.472 total

S>Меня смутил ретурн вот здесь

S>

S>                if(has_k_zeros(n[i], k, leftover))
S>                {
S>                    std::cout << p << std::endl;
S>                    return 0;
S>                }
S>

Это же return из main. Там раньше был еще return 1 на случай ненахождения результата, но я потом его убрал.

До последнего не верил в пирамиду Лебедева.

Re[11]: И снова об STL

	От:	Seon
	Дата:	22.12.08 10:53
	Оценка:

Здравствуйте, Roman Odaisky, Вы писали:

RO>делают одно и то же.

Ну и что же... зато запись какая!

RO>

RO>    ++*--dst;
RO>

КУЛ

Re[4]: k нулей

	От:	Seon
	Дата:	22.12.08 10:58
	Оценка:

Здравствуйте, Pro100Oleh, Вы писали:

PO>Здравствуйте, vadimcher, Вы писали:

V>>Было бы здорово, если бы все еще свой код выкладывали. Просто интересно сравнить эффективность/простоту для разных языков.

PO>Имхо, суть не в применяемых языках, а в алгоритме. Все приведенные здесь примеры что я пересмотрел (все не смотрел — лень) производят умножения по одной цифре. Я же использую int64 с 17 цифрами, то есть я умножаю в 17 раз быстрее.
PO>Кстати, основная сложность не в умножении, а в проверке числа. Здесь у меня другая оптимизация, но это пока секрет

.

Вот вас и просят показать свой алгоритм...
Интересно как это вы в инт64 впихнули 17 цифр

вы говорите в 17 раз быстрее...

У вас на 4 кирпичах — a(11) — 10 минут
У меня на 1 кирпиче — а(11) — 47 минут

Где же тут в 17 раз быстрее? интересно

Re[5]: k нулей

	От:	Seon
	Дата:	22.12.08 10:59
	Оценка:

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Seon, Вы писали:

S>>Не понял, почему вырождается?

E>потому, что "2 в степени 666" в 8-ричной системе записывается как 1 с 222 нулями

ААААА. Понятно! не то подумал

Re[4]: И еще одна программа на C++

	От:	Seon
	Дата:	22.12.08 11:07
	Оценка:

Здравствуйте, Roman Odaisky, Вы писали:

RO>

RO>~/src :) time ./kzeros 7
RO>6801
RO>./kzeros 7  0.12s user 0.00s system 100% cpu 0.124 total
RO>~/src :) time ./kzeros 8
RO>...10000...
RO>14007
RO>./kzeros 8  0.46s user 0.01s system 99% cpu 0.472 total
RO>

Мдя... медленновато.

Вы тратите много времени на перевод в 10-ю, видимо.
Мы тутачки работаем ужо сразу в десятичной.
14007 считается — 1-2 секунды.

S>>Меня смутил ретурн вот здесь
S>>

S>>                if(has_k_zeros(n[i], k, leftover))
S>>                {
S>>                    std::cout << p << std::endl;
S>>                    return 0;
S>>                }
S>>

RO>Это же return из main. Там раньше был еще return 1 на случай ненахождения результата, но я потом его убрал.

Та при чем тут 0 или 1. Зачем вываливаться из цикла как только нашли результат? Не уж-то нельзя продолжить поиск следующего числа?
Зачем потом тратить время опять на умножение сначала?

Re[12]: И снова об STL

	От:	Roman Odaisky
	Дата:	22.12.08 11:38
	Оценка:

Здравствуйте, Seon, Вы писали:

S>Ну и что же... зато запись какая! :super:
RO>>

RO>>    ++*--dst;
RO>>

С тем же успехом можно было ++dst[-1].

До последнего не верил в пирамиду Лебедева.

Re[5]: k нулей

	От:	Pro100Oleh
	Дата:	22.12.08 12:28
	Оценка:

Здравствуйте, Seon, Вы писали:

S>Здравствуйте, Pro100Oleh, Вы писали:

PO>>Здравствуйте, vadimcher, Вы писали:

V>>>Было бы здорово, если бы все еще свой код выкладывали. Просто интересно сравнить эффективность/простоту для разных языков.

PO>>Имхо, суть не в применяемых языках, а в алгоритме. Все приведенные здесь примеры что я пересмотрел (все не смотрел — лень) производят умножения по одной цифре. Я же использую int64 с 17 цифрами, то есть я умножаю в 17 раз быстрее.
PO>>Кстати, основная сложность не в умножении, а в проверке числа. Здесь у меня другая оптимизация, но это пока секрет

.

S>Вот вас и просят показать свой алгоритм...
S>Интересно как это вы в инт64 впихнули 17 цифр

S>вы говорите в 17 раз быстрее...

S>У вас на 4 кирпичах — a(11) — 10 минут
S>У меня на 1 кирпиче — а(11) — 47 минут

S>Где же тут в 17 раз быстрее? интересно

В 17 раз — имеется ввиду теоретическое улутчение в операции умножения, так как я за раз умножаю 17 цифр, а не одну. Но кроме самого умножения выполняются и проверка на нули. Кстати, здесь минус моего алгоритма, так как мне приходится искать втутри многоцифренномго числа нули.
На самом деле можно использовать даже 18 цифр, потому что мы используем только умножения на два: (10е18-1)*2 < Int64.MaxValue = 9,223,372,036,854,775,807. По поводу алгоритма — чуть розже, так как с сегодняшнего дня я в отпуске, а код остался на работе.

Pro

Re[5]: k нулей

	От:	Pro100Oleh
	Дата:	22.12.08 12:31
	Оценка:

Кстати, я использую не все 17 цифр. Это связанно с эвристикой

Pro

Re[5]: И еще одна программа на C++

	От:	Roman Odaisky
	Дата:	22.12.08 12:40
	Оценка:

Здравствуйте, Seon, Вы писали:

RO>>

RO>>~/src :) time ./kzeros 7
RO>>6801
RO>>./kzeros 7  0.12s user 0.00s system 100% cpu 0.124 total
RO>>~/src :) time ./kzeros 8
RO>>...10000...
RO>>14007
RO>>./kzeros 8  0.46s user 0.01s system 99% cpu 0.472 total
RO>>

S>Мдя... медленновато. :-\

S>Вы тратите много времени на перевод в 10-ю, видимо.
S>Мы тутачки работаем ужо сразу в десятичной.
S>14007 считается 1—2 секунды.

Написано же — 0,46 с.

S>Зачем вываливаться из цикла как только нашли результат? Неужто нельзя продолжить поиск следующего числа?
S>Зачем потом тратить время опять на умножение сначала?

Чтобы не усложнять.

До последнего не верил в пирамиду Лебедева.

Re[13]: И снова об STL

	От:	Seon
	Дата:	22.12.08 13:00
	Оценка:

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, Seon, Вы писали:

S>>Ну и что же... зато запись какая!

RO>>>

RO>>>    ++*--dst;
RO>>>

RO>С тем же успехом можно было ++dst[-1].

А ВОТ и НЕТ!
++*--dst; — уменьшает dst!
а ++dst[-1] — НЕТ!!!!!

|< < 1 2 3 4 5 6 7 8 9 10 > >> >|

Переместить
Удалить
Выделить ветку

Пока на собственное сообщение не было ответов, его можно удалить.

Заголовок: