treating an entire array as a humungous integer?

[kroz]

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!

[dedndave]

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.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

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   

[FORTRANS]

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.

[dedndave]

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

[MichaelW]

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:

Code Select Expand


;==============================================================================
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.

Code Select Expand


;==============================================================================
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


[kroz]

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 :)

[FORTRANS]

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.