Extension of the number range

[Gunther]

Related to another thread, I'm thinking about how to use larger numbers. Currently I am using 64 bit unsigned integers. This is pretty simple
and the valid number range goes up to 18 446 744 073 709 551 615; that's quite a lot.

For larger values, one could of course use REAL10 and apply the good old FPU. There seems to be enough air upwards for the moment. There
would be some minor problems with the particular algorithm, but they are all solvable.

For a basically long-term solution, probably one would have to use a arbitrary-precision arithmetic library. For that, there's a sufficient choice,
for example:

• longer-int. Was maintained until 2018.
• LibTom. Seems to be under active development.
• CLN. But it has as background C++.

To name just these. There are far more of them. Does anyone have experience with such libraries and have used them before in an assembly
language procedure?

I am very thankful for any hints and help.

[FORTRANS]

Hi,

   Perhaps a bit off topic, but I started to write an "arbitrary-precision"
fixed point set of routines.  So that might be an option for you.  If your
requirements are simple, then a complete library would not be needed.
I got addition, subtraction, multiplication, division, read, and display
written.  Never got around to negative numbers though.  Or cleaning
things up so I could follow what the code was doing after a few years.
But writing individual routines was easy.  Getting everything to work
together was a bit time consuming though.

Cheers,

Steve N.

[Gunther]

Steve,

thank you for your fast answer. 

   Perhaps a bit off topic, but I started to write an "arbitrary-precision"
fixed point set of routines.  So that might be an option for you.

That would be just right for that purpose.

If your requirements are simple, then a complete library would not be needed.
I got addition, subtraction, multiplication, division, read, and display written.

That fits perfectly. I only need addition, multiplication, division by 2 and the display of the values for the algorithm.
You can find the details in the archive collatz1.zip of this thread.

It's absolutely correct: Using a library like CLN would be like using a sledgehammer to crack a nut.

[daydreamer]

Check astronomical number thread, shows bcd and big integer calculation in asm,here used for huge fibonnaci numbers
http://masm32.com/board/index.php?topic=9773.0

[Gunther]

daydreamer,

Check astronomical number thread, shows bcd and big integer calculation in asm,here used for huge fibonnaci numbers

thank you for the hint. For Win64 programs BCD arithmetic isn't possible.

[mineiro]

Hello sir Gunther, I tried other approach instead of dealing with binary.
I choose separate the whole input string digits in memory bytes, so will be more easy to print each step. If it's not necessary print each iteration so this is not the best way.
Code need be washed to be more compreensible, but it's working.

linux64 code:

Code: [Select]

;uasm -elf64 collatz1.uasm
;gcc collatz1.o -o collatz1 -no-pie -lc

.X64

guint32 typedef dword
guint64 typedef qword
gpointer typedef qword

exit proto :dword
printf proto systemv pformat:PTR, arg:VARARG

;-------------------------------------------------------------
;Linux calling conventions, ABI
;-------------------------------------------------------------
;   call     rdi,rsi,rdx,rcx,r8,r9
;rbx rbp r12 r13 r14 r15 should be preserved between calls

.data?

.data
;cin db "90",0                ;collatz input string, I was thinking in getting that from command line or from some text file
cin db "2132156489789654310232165489798765498765432106598735432168797",0                ;collatz input string
align 16
cbuffer db 80 dup (0)           ;should be bigger than cin; how much!? I don't know


.code
align 16
main proc uses rbx rbp r12 r13 r14 r15 _argc:dword,_argv:ptr

local argc:guint32
local argv:gpointer

local phigh:guint64         ;pointer to high most (left) digit in input collatz string
local plow:guint64          ;pointer to lower (right) digit in input collatz string
local vaium:guint64         ;carry


mov argc,_argc
mov argv,_argv

lea r12,cin                 ;pointer to input collatz string, ended with 00h
mov r13,sizeof cin          ;db "2",0h == 2
sub r13,1                   ;-1 is necessary
add r12,r13                 ;pointer to tail (right most digit), 00h
dec r12                     ;"2"
lea r14,cbuffer             ;output buffer
add r14,sizeof cbuffer      ;sizeof output buffer
dec r14                     ;zero based

;convert (string to uint) and copy input collatz string into output buffer
;----------------------
.while r13 != 0
    movzx rax,byte ptr [r12]
    and rax,0fh             ;0-9 - decimal base assumed
    mov byte ptr [r14],al
    dec r12
    dec r14
    dec r13
.endw
;----------------------


mov r13,sizeof cin          ;strlen-1, mem alloc
dec r13
lea r14,cbuffer
mov phigh,r14               ;left most digit in value
mov plow,r14               
add plow,sizeof cbuffer     ;right most digit in value
dec plow



continue:
call print_number           ;
;int 3h
mov rax,phigh
mov rdx,plow
movzx rax,byte ptr [rdx]        ;right most digit
and rax,1                       ;is even or odd?
.if rax == 0                    ;even; divide by 2
    mov r15,phigh
    .while plow >= r15          ;left to right operation
        .if plow == r15         ;phigh == plow!?, last right digit reached
            shr byte ptr [r15],1
            jmp @F              ;done
        .endif
        shr byte ptr [r15],1        ;divide by 2
        .if carry?                  ;the right most bit of this byte was 1?
            add byte ptr [r15+1],10 ;so, we need increase by choosen base
        .endif
        inc r15                     ;next right digit in value
    .endw
    @@:
    ;check if we reach 000000000001 ;last possible value
    mov rax,phigh
    mov rcx,sizeof cbuffer
;    dec rcx
    xor rdx,rdx
   
    .while byte ptr [rax] == 0          ;all digits-1 in buffer are zero?
        inc rdx
        inc rax
        dec rcx
    .endw
   
    mov rcx,sizeof cbuffer              ;so, the last right digit is 1!?
    dec rcx
    .if rdx == rcx
        .if byte ptr [r15] == 1         ;yes, done, end this process
            jmp done
        .endif
    .endif
    jmp continue                        ;no, can be 2,3,4,..., so repeat
   
.else                               ;odd, multiplication, right to left
    mov r15,phigh
    mov rdx,plow
    mov vaium,0                     ;carry
    @@:
    movzx rax,byte ptr [rdx]        ;right most digit from plow
    .if rdx == plow
        lea rax,[rax*2+rax+1]       ;right most digit? So, *3+1
    .else
        lea rax,[rax*2+rax]         ;its not right most digit, so mul by 3
    .endif
   
    add rax,vaium                   ;carry
    mov vaium,0                     ;carry =0
    .while rax > 9                     ;base 10
        inc vaium
        sub rax,10
    .endw
    mov byte ptr [rdx],al
    dec rdx
    .if rdx != r15
        jmp @B
    .endif
    jmp continue
.endif

done:

exit1:
invoke exit,0

main endp



print_number proc uses rbx rbp r12 r13 r14 r15

    lea r12,cbuffer
    mov r13,sizeof cbuffer
    .while r13 != 0         ;ignore left zeros from digit in buffer
        .if byte ptr [r12] == 0h
            dec r13
            inc r12
        .else
            jmp @F
        .endif
    .endw
@@:
    .while r13 != 0
        movzx rax,byte ptr [r12]
        invoke printf,CStr("%d"),rax        ;print digit string
        dec r13
        inc r12
    .endw
   
    invoke printf,CStr(10)          ;print new line windows=13h,10h linux=10h
ret
print_number endp
end main


[Gunther]

mineiro,

thank you for your post and your remarkable ideas. 

That's very good and could be a way to move forward. Unfortunately I can' t test your code. Please, let me explain this briefly.

I don't have UASM installed and I've good reasons for that. I write my Win64 programs with the MASM64 SDK; it contains everything I need for this.

I have been a Linux user since kernel 1.2. This was at a time when many did not even know that this operating system existed. But a few years ago
I removed all Linux installations that were still running; the reason is simple. For more than 10 years, a Linux High Society Jetset has been established
among the developers. I'm sick and tired of these guys.

The only free Unix that runs on my system is FreeBSD. The system is completely solid and when programs are installed, they are always compiled from
the sources. In the end, you pretty much know what you've on your computer. There I use either NASM or GAS as assembler, depending on what I feel
like doing.

These are the reasons why I cannot help. This has nothing to do with you or your code. I hope you understand.

[mineiro]

Hello sir Gunther;
I will convert (optimize, better comments) that code to win64 ml64 assembler. I can only test final executable with wine, but should be ok.

[Gunther]

Mineiro,

I will convert (optimize, better comments) that code to win64 ml64 assembler.

thanks for your effort.

I can only test final executable with wine, but should be ok.

I think this will work well.

[mineiro]

This is win64 console version, I removed waitkey from code, so it's necessary open a console window and execute from there.

Fixed an input/output buffer overwrite.
I don't know how much digits vc_scanf can deal. Inserted a limit of 1022 input digits. If want more digits it's necessary create new executable.

[daydreamer]

This is win64 console version, I removed waitkey from code, so it's necessary open a console window and execute from there

great miniero

[Gunther]

Mineiro,

This is win64 console version, I removed waitkey from code, so it's necessary open a console window and execute from there.

that looks good. 

I will look at the code later to understand what you did. A few more comments would be helpful. That'll go off all right.

[mineiro]

Hello sir daydreamer;
I emphasize that this is just an example.
The program needs tweaking. It is necessary check for valid strings, the user can enter only "zeros" as input for example.
This should allocate memory instead of using a buffer in the data section as I used to.

A counterpoint is possible to make changes of number bases more easily as an attemp to see if patterns appears.

My intention is not to prove whether Collatz's conjecture is true or false; I just think now how it might be useful in some application. I have a vague idea of ​​how I can take advantage of such a conjecture, but tests are needed.

Hello sir Gunther;
I will comment the source code the most that I can and attach only source with more comments in next post.

[Gunther]

Mineiro,

I will comment the source code the most that I can and attach only source with more comments in next post.

You're really very hardworking. 

[mineiro]

I'm not good with english language. This is the best that I can do.
It's necessary some checks like invalid user input ( not between "0" to "9") or valid user input but only "zeros" or just "1".
The input string can be increased, will be better allocate zero memory to buffers instead of use buffers in data section as show in this example.

Code: [Select]

    include \masm32\include64\masm64rt.inc
    option casemap: none

NL equ 13,10

    .data

number  db "%d",0

strf    db "%s", 0              ; string format
uint64f db "%llu",0             ; 64 bit unsigned integer
str_NL  db NL, 0                ; new line
msg0    db "***********************************************", NL
        db "* The start is an arbitrary natural number N. *", NL
        db "* The input needs no periods and commas.      *", NL
        db "* Max input digits = 1022.                    *", NL
        db "***********************************************", NL,NL,0
msg1    db "Please make your input:     ", 0
msg2    db "Your start value is: N(", 0
msg3    db ") = ", 0
msg3A   db "It's an even number.", NL, 0
msg3B   db "It's an odd  number.", NL, 0
msg4    db "This leads to the following Collatz Sequence:", NL
        db "---------------------------------------------", NL, NL, 0
msg6    db "Done.", NL, 0
msg9    db "N(", 0
err0    db "Not enough memory, quiting", 0

i       dq 0                    ; value counter

;addval  dq 1
;mulval  dq 3

sz_input dq 0                ;input string size
sz_buffer dq 0               ;converted string to byte BCD size
_carry dq 0                  ;arithmetical carry

;---------------------------------
;p_buffer size = 8+1024 = 1030 bytes (digits)
;this buffer filled with zeros should be bigger than input user sequence bellow to avoid overflow
;while calculating odd collatz number.
;I limited value in code instead of here in data section.
p_buffer dq 0                   ;input string converted to byte based BCD buffer
db 1024 dup (0)                 ;If you want more input digits, increase this value
                                ;Will be better if allocate zeroed memory in code
;---------------------------------
N       dq 0                    ; pointer to input string buffer
db 1024 dup (0)
;---------------------------------


    .code

main proc uses rbp rbx rdi rsi r12 r13 r14 r15

    ; Print input information.

    invoke   print_NL
    invoke   vc_printf, addr strf, addr msg0
    invoke   vc_printf, addr strf, addr msg1
   
    ; Scan user input
    invoke   vc_scanf, addr strf, addr N            ;get decimal input string and store at variable N
    ; user input size
    invoke   vc_strlen, addr N                      ;input string size (digits)
    ;bigger than reserved buffer?
    cmp rax,1024-2                                  ;buffer size = 1024+8
    jbe @F                                          ;Input string size is bigger than buffer size?
    invoke   vc_printf, addr strf, addr err0        ;not enough buffer memory
    invoke ExitProcess,rax                          ;exit
   
@@:
    mov      sz_input,rax
    mov      sz_buffer,rax
    add      sz_buffer,2                                  ;it's necessary alloc more memory than input digits because collatz sequence can increase
                                                          ;how much memory? I don't know; I'm supposing 2 extra digits to avoid overflow
                                                          ;eg: if user entered string "9", this means only one byte as input string and
                                                          ;one byte to buffer. But 9 is odd, so 9*3+1 = 28 and this means 2 bytes as buffer necessary.
                                                          ;Sizeof Buffer need be bigger than input string.
    invoke   vc_printf, addr number, sz_input
    invoke   print_NL
   
    ;TODO: instead of use a buffer in data section will be better alloc memory filled with zeros
    ;malloc
    ;invoke  RtlZeroMemory,addr p_buffer,sz_buffer         ;alloc memory filled with zeros
   

    ;copy input string digits to buffer, transform input decimal string into byte BCD
    ;eg: "1234"(31323334h) will be 01,02,03,04
    ;"1234"=N    01020304h=p_buffer
    mov rcx,sz_input
    lea r8,N
    lea r9,p_buffer
    add r9,2                                            ;2 extra digits to bypass suposed overflow; TODO: check overflow (if left most digit is 0)
@@:   
    movzx rax, byte ptr [r8]
    and rax,0fh                                         ;"1" will be 01h, "2" will be 02h
    mov byte ptr [r9],al
    inc r8
    inc r9
    dec rcx
    jnz @B
    ;From here we only deal with buffer and it's size, input string was converted and copied to buffer.
   
    ; Print the user input for start value.

    invoke   vc_printf, addr strf, addr msg2
    invoke   vc_printf, addr uint64f, i
    invoke   vc_printf, addr strf, addr msg3
    invoke  print_number,addr p_buffer, sz_buffer           ;print each digit in buffer
    invoke   print_NL

    ; Is the number odd or even?

    mov rdx,sz_buffer                           ;size of converted input string (byte BCD digits)
    lea r9,p_buffer                             ;pointer to input string (byte BCD digits)
    add r9,rdx                                  ;pointer+size = last string digit, it's zero based so it's
    dec r9                                      ;necessary decrease one
    movzx rax,byte ptr [r9]                     ;load right most BCD digit in string.
    and rax,1                                   ;result will be 0 or 1, even or odd
    jnz @F                                      ;not zero? odd
    invoke   vc_printf, addr strf, addr msg3A   ;print even message
    jmp next
@@:
    invoke   vc_printf, addr strf, addr msg3B   ;print odd message
next:


    ; Print the Collatz Sequenz message.

    invoke   vc_printf, addr strf, addr msg4
    invoke   print_NL

    ; Calculate the Collatz Sequenz.

MainWhileStart:

    mov rdx,sz_buffer                           ;buffer size
    lea r9,p_buffer                             ;pointer to byte based BCD buffer
    add r9,rdx                                  ;last digit
    dec r9                                      ;zero position based
    movzx rax,byte ptr [r9]                     ;right most digit is odd or even?
    and rax,1
    jnz odd_number
   
;even number                                    ;divide by 2, left to right operation
;If right most digit is even, it's necessary divide whole digits in value by 2. Will be a left most digit to right most digit operation.
;I'm dealing with decimal base, so, if right most "bit" of "BCD byte" is 1 means that a carry to right will occur.
;eg: user input was "90", converted to byte BCD will be 09h 00h; its even number:
;step1: divide (shr) 09h (00001001b) by 2, result is 04h (00000100b) and Carry flag set, goto next right digit
;step2: carry is 1? Yes; so add 10 (ten) to 00h.
;                   divide 10 by 2 and result will be 05h, ignore carry (remainder) because we reach right most digit in this value sequence
;       carry is 0? divide by 2
;Result = 0405h
   
    lea r8,p_buffer                             ;value left most digit pointer
                                                ;r9 = right most digit pointer
next_even_operation:
    cmp r9,r8                                   ;I reach right most digit in value?
                                                ;pointer to left most digit reach pointer to right most digit?
    jnz @F                                      ;no
    shr byte ptr [r8],1                         ;yes, divide by 2 ignoring carry flag
    jmp print_this_number                       ;done
@@:   
    shr byte ptr [r8],1                         ;divide by 2, right most bit of this byte is 1!?
    jnc @F                                      ;no
    add byte ptr [r8+1],10                      ;decimal base, add 10 to next right digit in this value
@@:
    inc r8                                      ;next digit
    jmp next_even_operation                     ;repeat


odd_number:
;    odd number                                 ;mul by 3 and sum 1, right to left operation
; If right most digit is odd, it's necessary multiply whole digits in value (buffer) by 3 and sum 1 to right most digit.
; Will be right most digit to left most digit operation.
;eg: user input was "91", converted to byte BCD will be 09h 01h; its odd number:
;step1: mul 01h by 3 and sum 1. I optimize this by starting _carry with 1.
;      _carry=1
;       01h*3+_carry = 4        ;right most digit in value
;       _carry=0
;       4 >= decimal base?
;                           No, so store 4 and switch to next left digit in value
;                           Yes, so keep subtracting 10 (ten) until value is < ten, store this result.
;                               after each subtraction, increase _carry by 1, will be added to next left digit
;step2: _carry = 0 from previous step
;       09h*3+_carry = 27+0=27
;       27 >= 10?         Yes, 27-10=17      _carry=1
;       17 >=  10?         Yes, 17-10=7       _carry=2
;       7 >= 10?         No, store 7 and get next left digit

;step3: _carry = 2 from previous step
;       00h*3+_carry = 0+2=2
;       _carry = 0
;       2 >= 10?        No, store 2 and get next left digit
;Result = 020704h


    mov _carry,1                                ;+1
    mov rdx,sz_buffer                           ;buffer size (bigger than input string)

    cmp rdx,0                                   ;whole buffer done?
    jz print_this_number                        ;done

next_odd_operation:

    movzx rax,byte ptr [r9]                   ;read right most byte BCD digit
    lea rax,[rax*2+rax]                       ;right most digit * 3
    add rax,_carry                            ;+1
    mov _carry,0                             
@@:
    cmp rax,9                                 ;is this digit in value bigger than decimal base?
    jbe @F                                    ;no
    sub rax,10                                ;yes, so keep subtracting 10
    inc _carry                                ;and incrementing carry.
    jmp @B
@@:
    mov byte ptr [r9],al                      ;store resulting value
    dec r9                                    ;next left digit in value
    dec rdx                                   ;buffer size
    jnz next_odd_operation
;    jmp next_odd_operation


print_this_number:           ;both operations reach here, even or odd, so next step is check if we reach number 2 as a signal to stop processing
call PrintResult                 ;print digits in value stored at buffer ignoring left zeros digits in value


;we reach last possible number? Yes=quit, No=repeat
    mov rcx,sz_buffer           ;buffer size
    lea rsi,p_buffer            ;pointer to buffer
@@:
    cmp byte ptr [rsi],0        ;left digits in value are zero?
    jnz @F                      ;no, so we do not reach end of this program
    dec rcx                     ;
    inc rsi
    jmp @B
@@:
    cmp rcx,1                     ;exist only one digit not zero in whole number?
    jnz MainWhileStart            ;no, continue processing
    cmp byte ptr [rsi],1          ;is this digit 1?
    jnz MainWhileStart            ;no, continue processing

;    waitkey                     ; wait for key stroke
    invoke   ExitProcess, 0
    ret
main endp


; Purpose:   Print the iteration results.
; Input:     None
; Output:    Iteration number and result on the screen.
PrintResult proc
    inc i
    invoke   vc_printf, addr strf, addr msg9
    invoke   vc_printf, addr uint64f, i
    invoke   vc_printf, addr strf, addr msg3
    invoke  print_number,addr p_buffer, sz_buffer           ;print each digit in buffer
    invoke   print_NL
    ret
PrintResult endp


; print_NL
; Purpose:   Print New Line to STDOUT via libc.
; Input:     None.
; Output:    NL at STDOUT.
print_NL proc
    lea      rcx, strf          ; rcx -> format string
    lea      rdx, str_NL        ; rdx -> NL
    call     vc_printf          ; transfer to libc
    ret
print_NL endp


; print_number p_buffer,sz_buffer
; Purpose:   Print BCD number(s)
; Input:     p_buffer: pointer to byte based BCD number
;            sz_buffer: p_buffer size in bytes
; Output:    string number at STDOUT.

print_number proc uses rbp rbx rdi rsi r12 r13 r14 r15      ;p_buffer (rcx),sz_buffer(rdx)
    mov r12,rcx     ;p_buffer
    mov r13,rdx     ;sz_buffer
   
@@:
    cmp byte ptr [r12],0                ;ignore (don't print) left zeros from this number
    jnz @F
    inc r12                             ;next byte BCD number
    dec r13                             ;sz_buffer = sz_buffer -1
    jmp @B
@@:
    movzx rax,byte ptr [r12]            ;load one byte BCD number
    invoke   vc_printf, addr number, rax    ;print this number
    inc r12                             ;next BCD number
    dec r13                             ;decrease sz_buffer
    jnz @B

ret
print_number endp

end


--------edited----------
I'm rewriting this code to check for overflow. I was testing input string "77031" and program ended as expected (because this conjecture have a tendency to reach 1, well, the eternal loop only happens when reach 4,2,1,4,2,1, ...).
But iteration 100 to 101 was wrong in result.
So, post in next topic a new version.