Что нового

[Математика] Функция разложения числа на множители

Rioran

Everything is possible and achievable.
Сообщения
26
Репутация
2
AutoIt: Тестировалось на 3.3.12.0
Версия: 1.03

Категория: Вспомогательные функции, Строки, Математика.

Описание: Функция раскладывает число на множители и возвращает строку, где множители разбиты через символ звёздочки. Можно использовать в комбинации со StringSplit по символу "*" для получения массива множителей. Алгоритм показывает высокую производительность при работе с 19-ти значными числами.

Код/Пример:
Код:
Global $nNumber = 13414 ; Какое число разбиваем на множители
ConsoleWrite($nNumber & " = " & GetFactors($nNumber) & @CRLF)

func GetFactors($nVal)
; Автор VBA алгоритма:      Михаил "МСН", Источник: http://www.excelworld.ru/forum/7-18491-154442-16-1439576282
; Автор реализации на Au3:  Роман Rioran Воронов от 16 сентября 2015
; ----------------------------------------------------------------------
; Функция раскладывает число на множители и возвращает строку, где множители разбиты через символ звёздочки
; Function returns string of prime factors of given number, joined by asterisk sign
   Local $sText, $X = 3
   while IsInt($nVal / 2) And $nVal > 3
	  $nVal /= 2
	  $sText &= "*2"
   WEnd
   While $X*$X <= $nVal
	  If IsInt($nVal / $X) Then
		 $nVal /= $X
		 $sText &= "*" & $X
	  Else
		 $X += 2
	  EndIf
   WEnd
   return StringMid($sText & "*" & $nVal, 2)
EndFunc


История версий:
1.00: первая публичная версия
1.01: поправка для простых чисел - удалён лишний символ.
1.02: упрощён синтаксис с помощью операторов с присвоением и проверки делимости через IsInt.
1.03: теперь переменная Х инициализируется с присовением значения.

Источник: excelworld.ru

Автор(ы):
Автор VBA алгоритма: Михаил "МСН"
Автор реализации на Au3: Роман "Rioran" Воронов
 

AZJIO

Меценат
Меценат
Сообщения
2,874
Репутация
1,194
Rioran
Число двоек можно получить так
Код:
Int(Log($Value) / Log(2))
 
Автор
Rioran

Rioran

Everything is possible and achievable.
Сообщения
26
Репутация
2
AZJIO, спасибо, интересный вариант. Однако у меня не получается прикрутить его так, чтобы размер кода и количество операций сократилось или осталось тем же. Однако, это натолкнуло меня на мысль использовать IsInt для упрощения проверок.

Skif_off, это будет уже другая функция. Вам нужно разбить число на степени двойки? 13 = 8 + 4 + 1? Нужная функция на сайте уже есть ЗДЕСЬ, достаточно только, перебирая строку двоичного числа, заменять единички на двойку в степени "номер позиции справа минус один". Хотя ту функцию для 10-тичной системы можно было бы упростить. Если я Вас правильно понял - подтвердите - то могу написать такую функцию.
 

Skif_off

Знающий
Сообщения
173
Репутация
12
Rioran, да, имел в виду 13 = 1+4+8 и 0:rofl: = 0x1+0x4+0x8, если возможно и не отнимет много времени.
 
Автор
Rioran

Rioran

Everything is possible and achievable.
Сообщения
26
Репутация
2
Skif_off, готово, приглашаю с этим вопросом перейти в новую созданную мной тему ЗДЕСЬ. Общий алгоритм разложения на слагаемые степени двойки сделал, все хотелки оставлять там.
 

Andrey_A

Продвинутый
Сообщения
319
Репутация
68
Алгоритм показывает высокую производительность при работе с 19-ти значными числами
Алгоритм быстр, но для больших чисел не точен
Вот 18-ти значное число, которое является простым 948013690567935577
Функция его раскладывает на 2*2*2*2*2*2*2*47*59*199*13421519711 - хотя делать этого не должна, при умножении будет другое число.
Даже если IsInt, который ошибается, заменить на Mod, то результата с этим числом мы не увидим, т.к. надо будет дождаться, когда цикл пробежит 973 659 946 раз (возможно меньше, но всё равно много и долго). Для больших цифр нужно что-то другое, как минимум в начале проверять на простоту числа, а лучше в 3-х местах...
 
Последнее редактирование:

Oki

Продвинутый
Сообщения
452
Репутация
62
Алгоритм быстр, но для больших чисел не точен
Вот 18-ти значное число, которое является простым 948013690567935577
Функция его раскладывает на 2*2*2*2*2*2*2*47*59*199*13421519711
Дело не в неточности алгоритма, а в заблуждении топикстартера насчёт того, что настолько большие числа сохраняются полностью в переменных. Если и сохраняются, то только до того момента, пока кастятся в качестве текста. Как только настолько большое значение передаётся в качестве числа в стандарте IEEE 754, оно сразу приводится в форму, гарантирующую чётность. Наибольшее нечётное число, с которым так можно работать, равно 9007199254740991. Так что даже не всякое 16-значное число годится для подобной обработки. Специальные алгоритмы работы с большими числами разбивают числа на части в плане записи в какой-либо системе счисления и производят операции над частями, словно это цифры системы счисления с большим основанием, заботясь о том, чтобы промежуточные результаты всегда вписывались в то количество бит, которые отведены для хранения. Если этого не делать, то происходит округление в двоичной системе счисления. Начиная с одного порядка, все числа округляются до чётных, ещё выше - до кратных 4, затем - до кратных 8 и так далее.

А сам алгоритм в порядке. Когда в обиходе появятся 128-разрядные компьютеры, границы возможного расширятся автоматически. Но применять алгоритм нужно в рамках технических возможностей сегодняшнего дня. И это касается даже простейших арифметических операций, а не только сложных алгоритмов.
Код:
MsgBox(0, "", Int((9007199254740993 / 2) * 2)) ; на сегодня этот скрипт не возвращает 9007199254740993, но через десятки лет это может измениться
Ещё добавлю, что некорректно судить о скорости алгоритма разложения на множители, обобщая все числа одного порядка. Одно 19-значное число разложится быстро, другое - медленно. Даже когда всё работает корректно.
 
Последнее редактирование:

Oki

Продвинутый
Сообщения
452
Репутация
62
Процессоры давно поддерживают 128 бит.
Слова "в обиходе" надо было крупным шрифтом набрать?

Пока это не станет повседневностью, ни о какой поддержке 128-битной математики и мечтать не приходится.
 

Prog

Продвинутый
Сообщения
537
Репутация
65
Пока это не станет повседневностью
Шутите?
В каком году появились процессоры Pentium III? В них присутствуют инструкции SSE.
Поддержка 128 битных инструкций есть во всех x86 и x64 процессорах выпущенных за текущие 24 года.
 

Oki

Продвинутый
Сообщения
452
Репутация
62
Шутите?
В каком году появились процессоры Pentium III? В них присутствуют инструкции SSE.
Поддержка 128 битных инструкций есть во всех x86 и x64 процессорах выпущенных за текущие 24 года.
И как, например, в AutoIt обойти вот это препятствие, пользуясь этими средствами?
Код:
MsgBox(0, "", Int((9007199254740993 / 2) * 2)) ; на сегодня этот скрипт не возвращает 9007199254740993, но через десятки лет это может измениться
Очевидно, никак. Только программируя арифметику сверх возможностей процессорной. А поддержка длинных инструкций ни при чём.
 

Prog

Продвинутый
Сообщения
537
Репутация
65
И как, например, в AutoIt обойти вот это препятствие, пользуясь этими средствами?
Поскольку ассемблерные вставки AutoIt не поддерживает, придется писать в машинных кодах https://autoit-script.ru/threads/uznat-apparatnuju-podderzhku-processora.23921/#post-137278

На ЯП с поддержкой асма, все гораздо проще https://www.purebasic.fr/english/viewtopic.php?t=61309
Также можно воспользоваться другими возможностями процессора - аппаратным AES и SHA, которые значительно быстрее программных.

"Тормоз прогресса" это AutoIt, а не архитектура процессора.
Процы давно имеют инструкции не только для работы с 128 битными числами, но и с 256 и 512. https://en.wikipedia.org/wiki/AVX-512
Кому надо давно использует эти возможности.
Переход с x86 на x64 произошел только из-за ограничения доступного размера ОЗУ 4 ГБ. Если бы не это, до сих пор процессоры были бы 32-ух битными. Как понимаете перехода на 128 бит в ближайшей перспективе не будет. В этом нет необходимости.
 

Andrey_A

Продвинутый
Сообщения
319
Репутация
68
Поскольку ассемблерные вставки AutoIt не поддерживает
На немецком форуме есть несколько парней, которые это делают
Один из них Andy, которые показывают подключение к Assembler
Правда я ничего не понял )), но что-то интересное. Ряд примеров и сам ASM.au3 не заработал, потому что нет дополнительных UDF, которых нигде нет, т.к. обсуждения велись ещё лет 10 назад.
Возможно что для вас там найдётся (если вы это все знаете, то извиняюсь..)
Вот один из примеров, которые я когда-то нашёл...

Код:
;Liste der Primzahlen bis $maximum
;32-Bit Bytecode by Andy, eine der ersten Versionen, daher unoptimiert und "langsam"
Local $maximum = 1299709 ;Obergrenze der Primzahlen
Local $file = "Prim_" & $maximum & ".au3" ;Datei, in welche die Primzahlen geschrieben werden
$t = TimerInit() ;Timestamp sichern
$tStruct = DllStructCreate("uint Limit;uint Limes;char Mem[" & $maximum + 10 & "]") ;char, dann kann man nachher schön mit den stringfunktionen suchen
;die folgenden 4 Zeilen sparen einige Zeilen Assemblercode, außerdem kann man sich den Speicherinhalt in AutoIt anschauen
DllStructSetData($tStruct, "Mem", "001") ;die ersten 3 Zahlen setzen, 0=0 1=0 2=1 , 2 ist die erste Primzahl
DllStructSetData($tStruct, "Limit", $maximum);limit in die Struct schreiben
DllStructSetData($tStruct, "Limes", Floor(Sqrt($maximum)) + 1);wurzel aus limit in die struct schreiben
$bytecode = "0x558B6C24088B5D00B803000000C74405083130313083C00439D876F189EF83C70889FE8B4D00BB0300000089D8F7E0C604063001D839C87CF683C3023B5D007737803C1E3175F2535189D8BB0A00000031C931D2F7F3665280C10109C075F366580C30AAE2F9C6070D83C701595B3B5D047CB83B5D007CC1C607005DC3"
$tCodeBuffer = DllStructCreate("byte[" & StringLen($bytecode) / 2 & "]") ;Speicher für den bytecode reservieren...
DllStructSetData($tCodeBuffer, 1, $bytecode);...und mit dem Bytecode beschreiben
;die folgende Zeile startet den bytecode im Speicher und kehrt danach hierher zurück
$t = TimerInit() ;Timestamp sichern
$a = DllCall("user32.dll", "int", "CallWindowProcW", "ptr", DllStructGetPtr($tCodeBuffer), "ptr", DllStructGetPtr($tStruct), "int", 0, "int", 0, "int", 0);bytecode aufrufen, rückgabe in a[0]


$primzahlen = "2" & @CR & "3" & @CR & DllStructGetData($tStruct, "Mem");2 und 3 sind die ersten Primzahlen, dann folgt der Rest
$m = TimerDiff($t) ;Zeit seit Programmstart


FileDelete($file) ;Primzahldatei löschen
FileWrite($file, $primzahlen) ;Ausgabe der Primzahlen in Datei
$m1 = TimerDiff($t);Zeit seit Programmstart incl Datei schreiben


StringReplace($primzahlen, @CR, @CR, 0, 1) ;alle CR im String zählen.....auch AutoIt hat SPEEEEED^^
$anzahlprim = @extended ;hätte man auch vom Assembler zurückgeben lassen können^^


MsgBox(262144, "Primzahlen bis " & $maximum, $anzahlprim & " Primzahlen ermittelt in " & Int($m) & " Millisekunden" & @CRLF & _
"Primzahlen ermitteln und in Datei schreiben in " & Int($m1) & " Millisekunden." & @CRLF & _
"Ausgabe der Zahlen folgt in die Datei " & $file & @CRLF & _
"Die Primzahldatei wird nun angezeigt...")
ShellExecute($file) ;in Scite anzeigen
 

Oki

Продвинутый
Сообщения
452
Репутация
62
"Тормоз прогресса" это AutoIt, а не архитектура процессора.
Ладно, скажем тогда иначе: не "когда станут повсеместными 128-битные процессоры", а "когда хотя бы binary128 станет доступным в AutoIt". Суть выводов от этого не меняется. Даже если binary128 и binary256 на уровне процессоров поддерживаются. В текущих условиях скрипт топикстартера не предназначен для чисел выше указанного максимума. Но не по причине некорректности алгоритма, а по причине отсутствия этой поддержки.
Сообщение автоматически объединено:

которые показывают подключение к Assembler
Фактически ведь к машинным кодам. Другое дело, что до ассемблера недалеко, но всё-таки.
 
Последнее редактирование:

Prog

Продвинутый
Сообщения
537
Репутация
65
"когда хотя бы binary128 станет доступным в AutoIt".
Об этом спрашивайте у разработчиков AutoIt. Они решают что и когда добавлять в него.
Но если ответ будет никогда (или не в ближайшие годы), у вас выбор, отказаться от этой возможности или реализовать ее самому.

Даже если binary128 и binary256 на уровне процессоров поддерживаются. В текущих условиях скрипт топикстартера не предназначен для чисел выше указанного максимума.
Переписать и будет поддерживать. Если ничего не делать, ничего не будет...

Но не по причине некорректности алгоритма, а по причине отсутствия этой поддержки.
Асм вынести в dll или встроить в скрипт в виде машинного кода. Было бы желание, а сделать всегда можно.
 

Oki

Продвинутый
Сообщения
452
Репутация
62
Переписать и будет поддерживать. Если ничего не делать, ничего не будет...

Асм вынести в dll или встроить в скрипт в виде машинного кода. Было бы желание, а сделать всегда можно.
Всё это ради того, чтобы несколько увеличить количество цифр до нового лимита? Как по мне, если уж что-то и делать, то лучше переходить на арифметику больших чисел. Воскресивший эту тему Andrey_A как раз в параллельной теме заинтересовался библиотекой GMP, у которой не должно быть таких жёстких ограничений.
 

Prog

Продвинутый
Сообщения
537
Репутация
65
Можно совмещать.
Библиотека больших чисел с инструкциями 128+ бит. Это значительно ускорит вычисления.
 

Oki

Продвинутый
Сообщения
452
Репутация
62
Можно совмещать.
Библиотека больших чисел с инструкциями 128+ бит. Это значительно ускорит вычисления.
Полагаешь, что авторы библиотеки больших чисел не воспользовались сразу всеми возможностями внутри? В хорошем продукте должны бы.
Сообщение автоматически объединено:

Rioran
Число двоек можно получить так
Код:
Int(Log($Value) / Log(2))
AZJIO, спасибо, интересный вариант.
Так можно только получить максимальную степень двойки, которая не превосходит заданное число (да и то с риском неправильного результата в результате ошибок округления). Это не имеет ничего общего с разложением на множители. Например, пользы для разложения на множители числа 17 нет от информации о том, что такая максимальная степень - это четвёртая.
 
Последнее редактирование:
Верх