Что нового

Математика гипотеза Коллатца "3N+1", ускорение вычислений.[Решено]

All2khoff

Продвинутый
Сообщения
347
Репутация
65
Набрел в сети на интересную гипотезу Коллатца:
Если число нечетное то умножаем его на 3 и добавляем 1
Если число четное то делим его на два.
Любое целое положительное число если следовать алгоритму обязательно попадет в цикл 4-2-1
набросал в меру разумений скрипт.
Код:
#include <math.au3>
Global $I_Var, $a, $b=0

For $a=1 to 1000                        ;диапазон чисел
;~    ConsoleWrite("начинаем пересчет "&$a&@CRLF)
   mathc($a)
Next

Func mathc($I_Var)
   If $I_Var > 1 Then                        ;пока больше 1 условия выполняются
      $I_Result = _MathCheckDiv($I_Var, 2)    ;проверка числа чет-нечет
      Select
      Case $I_Result = -1 Or @error = 1        ;некорректное число
         ConsoleWrite("Неверное число"&@CRLF)
      Case    $I_Result = 1                    ;чило нечетное
;~          ConsoleWrite($I_Var&@CRLF)
         $b=$b+1                            ;счетчик итераций
         $I_Var = ($I_Var*3)+1
         mathc($I_Var)                        ;вызов следующей итерации
      Case $I_Result = 2                    ;число четное
;~          ConsoleWrite($I_Var&@CRLF)
         $b=$b+1                            ;счетчик итераций
         $I_Var = $I_Var/2
         mathc($I_Var)                        ;вызов следующей итерации
      Case Else                                ;неизвестная ошибка
         ConsoleWrite("Не удалось определить число"&@CRLF)
      EndSelect
   Else
      ConsoleWrite("закончили пересчет "& $a&@CRLF)
      ConsoleWrite("Количество итераций "& $b&@CRLF)
    $b=0                                    ;обнуление счетчика итераций
   EndIf
EndFunc

но в силу своей слабости в программировании не ведаю как ускорить процесс подсчета. прошу помощи в коррекции данной заготовки в сторону ускорения операции вычисления. хотябы количество итераций считать, на числах от 1000000.
Сам скрипт не является каким-то проектом и/или частью решения какой-то другой задачи, чисто для саморазвития.
 

Prog

Продвинутый
Сообщения
537
Репутация
65
Один из вариантов ускорения - написать на более "быстром ЯП". Будет ощутимое ускорение без изменения алгоритма.
 

Вложения

  • Test.zip
    4.6 КБ · Просмотры: 4
Автор
All2khoff

All2khoff

Продвинутый
Сообщения
347
Репутация
65
Спасибо конечно, но тут есть пару нюансов.
форум посвящен autoit и собственно тема открыта в попытках чуть глубже понять его возможности.
а еще ваш пример как я понял на PureBasic в диапазоне от 1 до 1000 отработал на 0.8 секунд дольше чем код на autoit. (не знаю в чем причина, чуть позже стал выполнятся в 3 раза быстрее.)
собственно яж не решение задачи пытаюсь найти. а просто научиться более менее грамотно в математику на autoit.
 

Prog

Продвинутый
Сообщения
537
Репутация
65
форум посвящен autoit и собственно тема открыта в попытках чуть глубже понять его возможности.
Верно, но речь шла про ускорение работы и я предложил вариант реального увеличения скорости. Подходит он или нет решайте сами.

как я понял на PureBasic в диапазоне от 1 до 1000 отработал на 0.8 секунд дольше чем код на autoit. (не знаю в чем причина, чуть позже стал выполнятся в 3 раза быстрее.)
Основное время тратится на вывод в консоль. Если закомментировать PrintN в процедуре mathc, вычисление производится примерно за 1 мс.
Вычисление миллиона чисел занимает около секунды. Эта задача хорошо параллелится и ее можно выполнить на нескольких ядрах процессора что дополнительно уменьшит время.
На AutoIt вряд ли получится добиться подобной скорости.
 

Вложения

  • Test.zip
    4.5 КБ · Просмотры: 5
Автор
All2khoff

All2khoff

Продвинутый
Сообщения
347
Репутация
65
верно основное время тратится на вывод.
потому почти все что идет в консоль я выключил
согласен что autoit не самый быстрый вариант, но пока мне интересны решения только на нём.
 

Prog

Продвинутый
Сообщения
537
Репутация
65
согласен что autoit не самый быстрый вариант, но пока мне интересны решения только на нём.
Немного оптимизировал.
Код:
#include <math.au3>

$Tim = TimerInit()
For $a=1 to 1000                        ;диапазон чисел
;~    ConsoleWrite("начинаем пересчет "&$a&@CRLF)
   mathc($a)
Next
ConsoleWrite("Time "& TimerDiff($Tim) &@CRLF)

Func mathc($I_Var)
    Local $a=$I_Var, $b=0
    while $I_Var > 1                        ;пока больше 1 условия выполняются
        $b+=1                            ;счетчик итераций
        if BitAND($I_Var, 1) Then                    ;чило нечетное
            $I_Var=($I_Var*3)+1
            ContinueLoop
        else                    ;число четное
            $I_Var=BitShift($I_Var, 1)
            ContinueLoop
        EndIf
    wend
    ConsoleWrite("закончили пересчет "& $a&@CRLF)
    ConsoleWrite("Количество итераций "& $b&@CRLF)
EndFunc
Конечно не миллисекунда как на PB, но быстрее чем было.
 

InnI

AutoIT Гуру
Сообщения
4,912
Репутация
1,429
Код:
$t = TimerInit()
For $i = 2 To 1000
  $c = 0
  $n = $i
  ;ConsoleWrite("Num " & $n & @CRLF)
  While $n > 1
    $n = BitAND($n, 1) ? $n * 3 + 1 : $n / 2
    ;$n = Mod($n, 2) ? $n * 3 + 1 : $n / 2
    $c += 1
  WEnd
  ;ConsoleWrite("Count " & $c & @CRLF)
Next
ConsoleWrite(TimerDiff($t) & @CRLF)
 
Автор
All2khoff

All2khoff

Продвинутый
Сообщения
347
Репутация
65
Спасибо за реакцию на мою задачу.
$n = BitAND($n, 1) ? $n * 3 + 1 : $n / 2

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

я посмотрел на справку BitAND но построение двух вариантов исчисления в одну строку я не понял как происходит и при каких условиях.
Немного оптимизировал.
#include <math.au3>
if BitAND($I_Var, 1) Then ;чило нечетное
$I_Var=BitShift($I_Var, 1)

как я понял ваш вариант, значимые операции выполняются здесь.
Bitshift - Сдвиг вправо эквивалентен делению на 2.
BitAND - Выполняет операцию побитового умножения (вот этот момент крайне непонятен)
для меня десятичная система исчисления крайне китайская грамота.
 
Последнее редактирование:
Автор
All2khoff

All2khoff

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

DyadyaGenya

Знающий
Сообщения
300
Репутация
10
Оч сложно, мой закостенелый мозг пока отказывается, от такой информации.
Ребят спасибо вам. есть куда думать и курить инструкции.
Тема решена.
и
построение двух вариантов исчисления в одну строку я не понял как происходит и при каких условиях

Вижу, что тема решена, но для меня варианты с BitAND и BitShift тоже сложноваты. И на самом деле я не математик, но для меня странно звучит, что людям не понятно, что деление четного числа на 2 всегда закончится 1, потому что умножение нечетного на 3 да плюс один будет четным. Тоесть система сама себя всегда залечит и станет четной. Тот же результат будет если вместо умножения на 3 будем только прибавлять 1. Итераций станет меньше, но результат тот же. Ну или скажем умножение на 5, тогда итераций станет больше, но результат тот же.
Поэтому как не математик и человек, который не очень разбирается в побитовых сдвигах предложил бы такой вариант, который основывается на самой простой для меня проверке на четность:
Код:
#include <math.au3>
$t = TimerInit()
For $i = 2 To 1000
  $c = 0
  $n = $i
;  ConsoleWrite("Число " & $i & @CR & @CR)
  While $n > 1
   If Mod($n,2)=0 Then
      $n = $n/2
;       ConsoleWrite("после $n/2 получили новое $n = " & @TAB & @TAB & @TAB & $n &@CR)
      $c += 1
   Else
      $n = $n*3+1
;       ConsoleWrite("после $n*3+1 превратили в новое четное $n = " & @TAB & $n &@CR)
      $c += 1
    EndIf
  WEnd
  ConsoleWrite("Итераций над числом " & $i & " получилось = " & $c & @CR & @CR)
Next
ConsoleWrite(TimerDiff($t) & @CRLF)

Получилось быстрее, чем у [B]Prog[/B], но медленее, чем у Inni
Ещё в моем случае скорость уменьшается, если отключить файл math.au3, а у Prog и Inni отключение на скорость не влияет. Так же замедлило скорость применение Select... Case... EndSelect, что очень странно. Возможно не правильно строю эту конструкцию.
$n = BitAND($n, 1) ? $n * 3 + 1 : $n / 2
Тоже хотелось бы понять запись. Вопрос даже не в BitAND. Он только сдвигает биты. Сама запись не понятна (знаки вопрос, двоеточия) По идее знак вопроса значит "или". Пробовал подставить, работает. А вот что значит двоеточие? Вообще, как сама запись расшифровывается?
 

InnI

AutoIT Гуру
Сообщения
4,912
Репутация
1,429
предложил бы такой вариант, который основывается на самой простой для меня проверке на четность
У меня в коде есть этот вариант. Он закомментирован, если вы не заметили.

как сама запись расшифровывается?
Чуть выше - мой ответ #9
 

DyadyaGenya

Знающий
Сообщения
300
Репутация
10
У меня в коде есть этот вариант. Он закомментирован, если вы не заметили.
Может он и такой же, но записан по другому. Потому и попросил пояснить, как читается ваша запись. Я её не понял.
Чуть выше - мой ответ #9
Я читал ссылку на вики. Там слишком мудрено написано. Общий смысл понятен, что проверяется истинность выражения, но как, я этого не понял. Хотя сейчас повторно прочитал, там оказывается есть пример на PHP. Вроде стало более менее понятно. И да, действительно у меня записано как второй вариант на PHP )))
Жаль, что сразу не обратил внимание. Грустно, что сразу не подумал про PHP. Ведь несколько раз применял такое сокращение. Правда и за PHP брался наверно последний раз весной.
Сообщение автоматически объединено:

Только вот все равно смотрю и понимаю, что прочитал бы его так: Если выражение $n = Mod($n, 2) истинно, то выполняем $n * 3 + 1, иначе $n / 2.
Но вот это меня и смущает. $n в любом случае будет равно Mod($n, 2). Только с разными остатками, либо с нулем, либо с остатком. С нулем - значит четное, если не ноль, то не четное. Так что все равно не до конца понимаю эту запись
 
Последнее редактирование:

IMStrelcov

CTPEJIbLLOB
Сообщения
253
Репутация
64
Сама запись не понятна (знаки вопрос, двоеточия) По идее знак вопроса значит "или". Пробовал подставить, работает. А вот что значит двоеточие? Вообще, как сама запись расшифровывается?
Код:
;И первый и второй варианты выполняют одно и тоже.
;Но второй вариант работает быстрее чем первый

;Первый вариант
If $Var_1 Then
   $Var_2 = 1
Else
   $Var_2 = 0
EndIf

;Второй вариант
$Var_2 = $Var_1 ? 1 : 0

;То есть:
;($Var_1) - это условие
;(?) - это Then
;(:) - это Else


Код:
;И первый и второй варианты выполняют одно и тоже.
;Но второй вариант работает быстрее чем первый

;Первый вариант
If BitAND($n, 1) Then
   $n = $n * 3 + 1
Else
   $n = $n / 2
EndIf

;Второй вариант
$n = BitAND($n, 1) ? $n * 3 + 1 : $n / 2

;То есть:
;($n) - это условие
;(?) - это Then
;(:) - это Else
 

InnI

AutoIT Гуру
Сообщения
4,912
Репутация
1,429
Если выражение $n = Mod($n, 2) истинно
Дело в том, что условие может выполняться (или не выполняться) без прямого сравнения.
Код:
$i = 1
; прямое сравнение
If $i > 0 Then ; условие выполнено
; косвенное сравнение
If $i Then ; в данном случае единица - это True и условие выполнено

If $i = 0 Then ; условие не выполнено
If Not $i Then ; условие выполнится когда $i станет нулём: ноль - это False, Not False - это True

Код:
; прямое сравнение
$n = (Mod($n, 2) > 0) ? $n * 3 + 1 : $n / 2
; косвенное сравнение
$n = Mod($n, 2) ? $n * 3 + 1 : $n / 2

Код:
; можно даже так
$i = 0
$i ? MsgBox(0,"",True) : MsgBox(0,"",False)
; AutoIt данную конструкцию выполнит, но AU3Check выдаст ошибку синтаксиса
; поэтому для запуска с AU3Check делаем присваивание ненужной переменной
$_ = $i ? MsgBox(0,"",True) : MsgBox(0,"",False)
$_ = Not $i ? MsgBox(0,"",True) : MsgBox(0,"",False)

; прямое сравнение в тернарном операторе, особенно при сравнении на равенство,
; рекомендуется заключать в скобки
$a = ($b = 5) ? 1 : 0

Правила преобразования типов при сравнении смотрим здесь:
 

DyadyaGenya

Знающий
Сообщения
300
Репутация
10
; прямое сравнение $n = (Mod($n, 2) > 0) ? $n * 3 + 1 : $n / 2 ; косвенное сравнение $n = Mod($n, 2) ? $n * 3 + 1 : $n / 2
От моего не совсем правильного понимая функции Mod() и незнания про прямое и косвенное сравнение я допускал, что правильно было бы так:
Код:
$n = (Mod($n, 2)=0) ?  $n / 2 : $n * 3 + 1

И для полного понимая хотел уточнить, если запись типа:
Код:
$n = [URL='https://autoit-script.ru/docs/functions/mod.htm']Mod[/URL]($n, 2)

То как autoit понимает, что это четное или не четное число. Потому что ради интереса попробовал поменять местами Then и Else:
Код:
$n = Mod($n, 2) ?  $n / 2 : $n * 3 + 1

И получил другой результат
У функции Mod() по умолчанию зашито типа "верный результат" - четное число?
 

InnI

AutoIT Гуру
Сообщения
4,912
Репутация
1,429
я допускал, что правильно было бы так
Так тоже правильно. Вообще все эти конструкции идентичны
Код:
$n = (Mod($n, 2) = 0 ) ? $n / 2 : $n * 3 + 1 ; прямое (явное) сравнение с нулём
$n = (Not Mod($n, 2) ) ? $n / 2 : $n * 3 + 1 ; косвенное (неявное) сравнение с инверсией результата Mod
$n = (    Mod($n, 2) ) ? $n * 3 + 1 : $n / 2 ; неявное сравнение с результатом Mod
$n = (Mod($n, 2) <> 0) ? $n * 3 + 1 : $n / 2 ; явное сравнение с числом, отличным от нуля


У функции Mod() по умолчанию зашито типа "верный результат" - четное число?
В справке указано
Успех:Возвращает остаток от целочисленного деления делимого на делитель.
Понимаете? Деление любого целого числа на любое целое число. Результат - остаток от деления.
Если в функцию подставить 7 и 4, то результатом будет 3.
В данном случае мы какое-то целое число делим на 2. Соответственно, если в результате ноль (нет остатка), то число чётное. Если единица (остаток от деления на 2), то число нечётное. В операциях сравнения, когда типы различны, AutoIt преобразует 0 в False, а любое другое число - в True. Это правило как раз и работает при неявном сравнении.
 

DyadyaGenya

Знающий
Сообщения
300
Репутация
10
Понимаете? Деление любого целого числа на любое целое число. Результат - остаток от деления.
Это я и сам несколько раз говорил
Соответственно, если в результате ноль (нет остатка), то число чётное. Если единица (остаток от деления на 2), то число нечётное.
Вот теперь понял окончательно. Спасибо.
 
Верх