Тривиальня задача о переборе символов.

Необходимо написать подпрограмму, которая бы последовательно генерировала m^n комбинаций, составленных из m набора (abc) элементов n-ой длинны в строке. Понятно что речь идет о простом переборе комбинаторных объектов (brute). Алгаритм должен быть оптимизирован по скорости как можно сильнее.



У меня нету серьезного опыта работы с fpu, я не владею большими познаниями в области машинных команд x86.

Мне нужно вычислить n^m. Искал в справочнике, но такой машинной команды не нашел, только те которые считают логарифмы и f2xm1 (2^x-1). значит нужно писать простой алгаритм:



mov ecx,3 ;cycles +1

mov eax,255d

mov ebx,eax ;lenght

muling:

mul ebx

loop muling



Полагаю можно сделать все гораздо проще и быстрее, только незнаю как. К тому же нужно учитывать, что комбинаций в моем случае будет заведомо больше 4-х миллиардов.



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

n=4

m="1234567890ABCDEF";

1. 0001

2. 0002

...

10^4. 9999

10^4+1. ?

...

x=m[m.lenght];

y=m[m.lenght-1];

...

m^n-1. xxxy = FFFE

m^n. xxxx = FFFF



Теперь я точно запутался.

 

Под "^" это степень? или же сишный xor?

 

степень конечно

 

NoName



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



Итак, исходя из описания не очень-то и понятно, что делать надо. Я не стану описывать все вопросы, что у мя возникли - непонятно чуть ли не все, начиная с первой фразы. генерировала m^n комбинаций, нужно вычислить n^m - мама, дык что тебе надо, все таки?



Посему.

1. Внятно сформулировать задачу.

2. Почитать сие: http://algolist.manual.ru/maths/combinat/index.php, а особенно, сие - http://algolist.manual.ru/maths/combinat/sequential.php



Что есть размещение? Сочетание? Возможно, мона поглядеть и это: http://main.soobcha.org/coding/vb/algorithms/

3. На псевдокоде или на любом ЯВУ написать общую идею твоей программы.

4. А вот далее уже мона говорить о низкоуровневой оптимизации.



А ты сразу с места в карьер полным ходом. Неудивительно, что прибалдел. Согласно дяде Кнуту: "преждевременная оптимизация - корень всех зол!".

 

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

 

я даун http://wasm.ru/print.php?article=cycle_pwd

 

Это очень просто.

Либо инкриментом либо декриментом.

Ты просто считаешь это n разрядным числом по основанию m.

Можно слева направо, можно справа налево.

Например с инкриминированием от младших к старшим.

Увеличиваешь младший, если он после инкриминирования меньше m - алгоритм закончен.

Нет - присваиваешь ему 0 и переходишь к следующему, с ним проводишь вышеупомянутую операцию. И так пока очередной по старшинству символ после инкриминирования не даст число < m. Переход понятно будет осуществлятся после инкриминирования младшего символа каждный m^1_ный раз, следующего m^2_ный раз... последнего 1 раз - что и есть конец - все "разряды" превратятся в 0 снова.

т.е. переходов (всех) будет m^(n-2)+m^(n-3)+..+m^0 = (m^(n-1))-1 столько же безпереходных инкриментов. Последный m^0 по сути уже не переход а окончание полного алгоритма.

Символы по сути не имееют значения - ты можешь использовать просто числа. Потом по таблице индексной заменить на символы.

Набросал пример в атаче. Можно даже слова а не символы

1593952637__Cartage.zip

 

Да сорс очень мощный, понадобится время для его разбору. Спасибо.

 

Вообщем с алгаритмом все более менее ясно. Работаем.



Нужна помощь в двух аспектах:

1. Пытаюсь найти как можно сделать нормальное возведение в степень числа.

2. объясните мне, ну непонимаю я. В чем преимущества использования fpu (кроме точности) перед cpu?

 

Преимуществ FPU перед CPU в твоей задаче ИМХО нет. Тебе просто нужно взять 64-битное целое.

Что касается самого вычисления -- чем обычное умножение m на себя n раз не устраивает? Вроде этот код не так уж и часто выполняться должен -- оптимизировать его смысла особого нет.

 

2 flankerx

Как я понял с помощью команды mul мне не получить число больше чем размер регистра eax. Это важный момент. Финальное число комбинаций получается огромным и непоместится в r32.

 

Пытаюсь найти как можно сделать нормальное возведение в степень числа



поиск по форуму рулит!



http://www.wasm.ru/forum/index.php?action=vthread&forum=17&topic=9475



http://www.wasm.ru/forum/index.php?action=vthread&forum=25&topic=8018



и вообще, не любишь ты искать, я смотрю

 

Да я смотрел уже и форум и все остально, но это не то! Эти линки помочь решить проблему r32 не могут, а алгаритм возведения в степень написан в самом верху.

Да, кстати говоря ясной разницы между fpu и cpu я неуслышал.

Как они хотябы в скорости?

 

Ничё не понимаю, зачем что-то в степень возводить?

Если m < 256 берёшь просто n байт массив где каждый байт будет разрядом. Зачем степень то вообще?

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

А в примере вообще легко например вывести все возможные конструкции структур опкода среди элементов можно также вводить "пустоту" которая даст "отсутсвие разряда" в каких то из картежей.

 

The Svin

Клиника...

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

 

Не понимаю что такое "наглядно видно".

Где это и зачем нужно быть "видно"?

И как должно быть видно.

Вот допустим m = 256 и n = 11

начальное число будет

00 00 00 00 00 ... 11 раз

на каком то этапе у тебя допустим получилась

01 AB FF 01 00 ... 00

Это именно уже само по себе число в 256 ричной системе





Нот этого числа - сколько ещё осталось тоже в 256 чиной системе. Сам картеж это уже число!

а m^n вообще будет константой 01 и 11 раз 00

Если тебе нужно число для выхода из алгоритма то этого вообще не надо! Проверкой на выход будет если после какой либо инкриминации получилось = m а разряд уже последний.



Любая степень в поддерживаемом типе будет ограничена размерностью типа. В виде же картежа она ограничений вообще не будет иметь (пока памяти хватит)

Ну не можешь ты получить да в QWORD величину если например m = 32000 а n = 2^1024 а в представлении слово на разряд - можешь.



Картеж уже будет числом в позиционной системе (в моём исходнике и не только в позиционной но можно задать в неабсолютной поместной)

Если ты под "наглядно видно" имеешь ввиду вывод на экран в десятичной системе, то тоже не возведение в степень тебя должно волновать а представление в виде десятичной системы числа по произвольному основанию.



Если бы символов было всего 3 то у тебя менялось бы

00 00 00 ...

01 00 00 ...

02 00 00 ...

00 01 00 ...

...

02 02 02 ...

Это само по себе уже число в троичной системе

Количество наборов было бы

00 00 00 ... 01 в троичной же т.е. n раз 00 и 1 в старшем разряде (байте). Можно вообще право налево расположить можно слева направо как хочешь.

Можем договорится например что сто пишется как

001 а можем как 100.

 

Да ну вас, fmulp и чтоб тихо было.

 

The Svin

он хочет туда втулить функцию подсчета оставшегося времени на все вычисления, для этого нада знать m^n, т.е. кол-во всех возможных комбинаций, ДО начала брутфорсинга, так?

 

http://www.rsdn.ru/article/alg/fastpow.xml

 

и при чем тут действительные числа... :-/