Hi everyone...
I've got this very big problem... I want to do arithmetic with numbers of 2^800 and beyond 0_o
so if I use GlobalAlloc, blah blah, and allocate say... 256 bytes, is there any algorithm to do mul and div
(add/sub is easier) to the entire array, treating it as a massive integer?
i.e -
ARRAY db 8 dup(AAh, BBh, CCh, DDh, EEh, 11h, 22h 33h)
and then divide ARRAY by an integer of size >32bits, treating ARRAY
as an integer that is == 0AABBCCDDEE112233h?
thanks!
you are talking about "arbitrary integers" or "bignums" - but i like your "humungous" better :lol:
the masm32 library does not have any bignum functions, but there are free libraries out there that do
one forum member, Drizz, has such a library
http://www.masmforum.com/board/index.php?topic=13068.msg101313#msg101313 (http://www.masmforum.com/board/index.php?topic=13068.msg101313#msg101313)
http://www.drizz.eu.pn/index.php?option=com_jotloader&view=categories&cid=0_ace66080c316578be4a59e0b372e58fa&Itemid=2 (http://www.drizz.eu.pn/index.php?option=com_jotloader&view=categories&cid=0_ace66080c316578be4a59e0b372e58fa&Itemid=2)
most bignum libraries support specific integer sizes of 256-bit and/or 512-bit widths
a few years back, i wrote 3 routines that convert large integers to ascii decimal strings :P
http://masm32.com/board/index.php?topic=222.0 (http://masm32.com/board/index.php?topic=222.0)
one is for unsigned, one is for signed, and one will handle either (mode selectable)
they handle integers of all practical sizes
there is also a routine in there that does large integer exponentiation
if you want to multiply and divide larger values, it isn't too hard to write "long-hand" routines
getting them to be super-fast is another issue :biggrin:
Hi,
Yes there are algorithms for bignum arithmetic. I got mine
from some books when I wrote a fixed point arithmetic package.
For example, a division routine was adapted from "Advanced
Assembly Language" by Steven Holtzner. Donald Knuth's
"Art of Computer Programming" calls it multiple-precision
arithmetic (another search term).
A quick look at my (16-bit) program shows it is about
2,000 lines long, of which about 1,000 seems to be debug,
display, comments, and timing code. Ick. A sample of the
main routines is FixDiv, FixDisp, FixA2B, FixCopy, FixAdd,
FixSub, FixMulA, FixMulM, and FixDispHex. Two multiplies
for different algorithms, not different usage. Fixed point has
some extra bookeepping over integer, but should be of the
same order of magnitude in size.
Regards,
Steve N.
before we go off on a tangent, we should examine why you need the precision of bignums :P
it may be that what you want to do can be done with the FPU
I'm assuming that your goal is to do the arithmetic, and not to start with some arbitrary array. For this purpose GMP is fast and easy to use. For this code I used the DLL and import library from the gmp-dynamic-vc-4.1.2 library here (http://cs.nyu.edu/exact/core/gmp/):
;==============================================================================
include \masm32\include\masm32rt.inc
includelib gmp.lib
;==============================================================================
;-----------------------------------------------
; Sorry, no time to translate the full headers.
;-----------------------------------------------
mp_limb_t TYPEDEF DWORD
__mpz_struct STRUCT
_mp_alloc DWORD ?
_mp_size DWORD ?
_mp_d mp_limb_t ?
__mpz_struct ENDS
__gmpz_init PROTO C :DWORD
__gmpz_set_str PROTO C :DWORD,:DWORD,:DWORD
__gmpz_init_set_str PROTO C :DWORD,:DWORD,:DWORD
__gmpz_clear PROTO C :DWORD
__gmpz_add PROTO C :DWORD,:DWORD,:DWORD
__gmpz_sub PROTO C :DWORD,:DWORD,:DWORD
__gmpz_mul PROTO C :DWORD,:DWORD,:DWORD
__gmpz_tdiv_q PROTO C :DWORD,:DWORD,:DWORD
__gmp_printf PROTO C :DWORD,:VARARG
;==============================================================================
.data
array dd 1,2,3,4,5
t0 __mpz_struct <>
t __mpz_struct <>
.code
;==============================================================================
start:
;==============================================================================
invoke __gmpz_init, ADDR t0
invoke __gmpz_init, ADDR t
invoke __gmpz_set_str, ADDR t0, chr$("999999999999999999999999999999"), 10
invoke __gmp_printf, cfm$("%Zd\n\n"), ADDR t0
invoke __gmpz_mul, ADDR t, ADDR t0, ADDR t0
invoke __gmp_printf, cfm$("%Zd\n\n"), ADDR t
REPEAT 20
invoke __gmpz_mul, ADDR t, ADDR t, ADDR t0
invoke __gmp_printf, cfm$("%Zd\n\n"), ADDR t
ENDM
REPEAT 21
invoke __gmpz_tdiv_q, ADDR t, ADDR t, ADDR t0
invoke __gmp_printf, cfm$("%Zd\n\n"), ADDR t
ENDM
inkey
exit
;==============================================================================
end start
Note that the structure and the protos in the above source represent only a very small part of the declarations in the GMP header files. A manual is available here (http://gmplib.org/manual/index.html).
;==============================================================================
include \masm32\include\masm32rt.inc
includelib gmp.lib
;==============================================================================
;-----------------------------------------------
; Sorry, no time to translate the full headers.
;-----------------------------------------------
mp_limb_t TYPEDEF DWORD
__mpz_struct STRUCT
_mp_alloc DWORD ?
_mp_size DWORD ?
_mp_d mp_limb_t ?
__mpz_struct ENDS
__gmpz_init PROTO C :DWORD
__gmpz_set_str PROTO C :DWORD,:DWORD,:DWORD
__gmpz_init_set_str PROTO C :DWORD,:DWORD,:DWORD
__gmpz_clear PROTO C :DWORD
__gmpz_add PROTO C :DWORD,:DWORD,:DWORD
__gmpz_sub PROTO C :DWORD,:DWORD,:DWORD
__gmpz_mul PROTO C :DWORD,:DWORD,:DWORD
__gmpz_tdiv_q PROTO C :DWORD,:DWORD,:DWORD
__gmp_printf PROTO C :DWORD,:VARARG
;==============================================================================
.data
array dd 1,2,3,4,5
t0 __mpz_struct <>
t __mpz_struct <>
.code
;==============================================================================
start:
;==============================================================================
invoke __gmpz_init, ADDR t0
invoke __gmpz_init, ADDR t
invoke __gmpz_set_str, ADDR t0, chr$("999999999999999999999999999999"), 10
invoke __gmp_printf, cfm$("%Zd\n\n"), ADDR t0
invoke __gmpz_mul, ADDR t, ADDR t0, ADDR t0
invoke __gmp_printf, cfm$("%Zd\n\n"), ADDR t
invoke GetTickCount
push eax
xor ebx, ebx
.WHILE ebx < 1000
invoke __gmpz_mul, ADDR t, ADDR t, ADDR t0
inc ebx
.ENDW
invoke GetTickCount
push eax
invoke __gmp_printf, cfm$("%Zd\n\n"), ADDR t
mov esi, eax
pop eax
pop edx
sub eax, edx
printf("%dms\t%d digits\n\n", eax, esi)
invoke GetTickCount
push eax
xor ebx, ebx
.WHILE ebx < 1001
invoke __gmpz_tdiv_q, ADDR t, ADDR t, ADDR t0
inc ebx
.ENDW
invoke GetTickCount
pop edx
sub eax, edx
printf("%dms\n\n", eax)
invoke __gmp_printf, cfm$("%Zd\n\n"), ADDR t
inkey
exit
;==============================================================================
end start
thanks for the links :)
well, I'm generally interested in big, big numbers, such as mersenne primes :)
so i'd be dividing n by x again and again until x=1/2(y), so maximum speed would be nice :)
Quote from: kroz on February 21, 2013, 04:03:46 PM
well, I'm generally interested in big, big numbers, such as mersenne primes :)
so i'd be dividing n by x again and again until x=1/2(y), so maximum speed would be nice :)
Hi,
Donald Knuth's "Art of Computer Programming" has in
section 4.3 Multiple-Precision Arithmetic , three subsections.
One of which is 4.4.4 How Fast Can We Multiply? He also
discusses division there. Later on there is 4.5.4 Factoring
into Primes. My copy is a bit old, so there may be some
changes in the current edition.
His discussion is mathematical and terse. And I found it
a bit "thick". But that was not the subject I bought the book
for, so just skimmed those sections. He does show an
implementation of some of the algorithms. I generally do
not get many of his explainations by reading them (other
sections). I have to try and code up his algorithms and
programs to see how or why they work. Sometimes I do
get the ideas the first time around though. YMMV.
And I am sure there are other books that discuss those
kind of ideas as well.
Regards,
Steve N.