1 Тема от DnsIs (изменено: DnsIs, 2023-11-07 13:06:55)

  • DnsIs
  • Участник
  • Неактивен

Тема: Алгоритм деления больших чисел.

Приветствую.

Я пишу на Lua, но это совсем не главное.

Нужно большое беззнаковое число разделить и получить целое и остаток. (в lua // - целое, % - остаток)
Беру число 0xAA1008F43D202A1D  = -6192439642543871459 = 12254304431165680157

Так вот lua работает со знаковым числом:

0xAA1008F43D202A1D // 0xB8AB7B9E) & 0xffffffff = 0x88DE614D        
0xAA1008F43D202A1D % 0xB8AB7B9E = 0x94B11D97

А мне нужен результат.

0xAA1008F43D202A1D // 0xB8AB7B9E) & 0xffffffff = 0xEBC02966
0xAA1008F43D202A1D % 0xB8AB7B9E = 0x71809B29
Нас невозможно сбить с пути, нам пофигу куда идти.

2 Ответ от teadrinker

  • teadrinker
  • Администратор
  • Неактивен

Re: Алгоритм деления больших чисел.

Какой-нибудь библиотекой воспользоваться?

bigInteger := WebRequest("https://peterolson.github.io/BigInteger.js/BigInteger.min.js")
js := GetJS()
js.eval(bigInteger)
res := js.eval("bigInt('AA1008F43D202A1D', 16).divmod(0xB8AB7B9E)")
MsgBox % "0x" . res.quotient.toString(16) . "`n0x" . res.remainder.toString(16)

WebRequest(url, method := "GET", HeadersArray := "", body := "", ByRef error := "") {
   Whr := ComObjCreate("WinHttp.WinHttpRequest.5.1")
   Whr.Open(method, url, true)
   for name, value in HeadersArray
      Whr.SetRequestHeader(name, value)
   Whr.Send(body)
   Whr.WaitForResponse()
   status := Whr.status
   if (status != 200)
      error := "HttpRequest error, status: " . status
   Arr := Whr.responseBody
   pData := NumGet(ComObjValue(arr) + 8 + A_PtrSize)
   length := arr.MaxIndex() + 1
   Return StrGet(pData, length, "UTF-8")
}

GetJS() {
   static Doc, JS
   if !Doc {
      Doc := ComObjCreate("htmlfile")
      Doc.write("<meta http-equiv=""X-UA-Compatible"" content=""IE=9"">")
      JS := Doc.parentWindow
      ( Doc.documentMode < 9 && JS.execScript() )
   }
   Return JS
}

Код на AHK v1, проще на Node.js.

Разработка AHK-скриптов:
e-mail dfiveg@mail.ru
Telegram jollycoder

3 Ответ от DnsIs

  • DnsIs
  • Участник
  • Неактивен

Re: Алгоритм деления больших чисел.

teadrinker Спасибо.

Сделал реализацию двоичного деления в столбик

Поковырял Ваш "BigInteger.js" но потом придумал свою реализацию для себя.
Но, делимое пришлось разбить на два 32-битных числа.

function div(a, b, c)

	local i, d, q = math.floor(2 ^ 32);

	q = (i % c) * a + b;
	d = (i // c) * a + q // c;
	q = q % c;

	return d, q

end

div(0xAA1008F4, 0x3D202A1D, 0xB8AB7B9E)

Нас невозможно сбить с пути, нам пофигу куда идти.

4 Ответ от teadrinker

  • teadrinker
  • Администратор
  • Неактивен

Re: Алгоритм деления больших чисел.

А делить только на 32-битное нужно?

div(0xAA1008F4, 0x3D202A1D, 0xFFFFFFFFF)
Разработка AHK-скриптов:
e-mail dfiveg@mail.ru
Telegram jollycoder

5 Ответ от DnsIs

  • DnsIs
  • Участник
  • Неактивен

Re: Алгоритм деления больших чисел.

teadrinker
Ну да, нужно было реализовать беззнаковое деление двух регистров на другой:

mov eax, 0x3D202A1D
mov edx, 0xAA1008F4
mov ecx, 0xB8AB7B9E
div ecx
Нас невозможно сбить с пути, нам пофигу куда идти.

6 Ответ от DnsIs

  • DnsIs
  • Участник
  • Неактивен

Re: Алгоритм деления больших чисел.

Так наверное правильнее и понятнее

function div(a, b, c)

	local Q, R, tmp;

	Q, R  = (a // c) << 32, a % c;
	tmp = ((R << 32) + b);
	Q, R = Q + (tmp // c), tmp % c;

	return Q, R

end
Нас невозможно сбить с пути, нам пофигу куда идти.