Author Topic: Handling exponents and printing large numbers to console or win32  (Read 385 times)

Chris.

  • Regular Member
  • *
  • Posts: 12
For my first program I decided to toy around with mathematical operations.
I wanted to make a simple program that asks for an input X and Y and then performs Y^x and then displays the result.

For Example entering 2^38 will produce 274,877,906,944 which I know cannot fit on a 32 bit register (because 4,294,967,295 < 274,877,906,944).

The code example(s) I am about to post originate from Stackoverflow at (https://stackoverflow.com/a/12681913).

Example 1:
Code: [Select]
xor edx,edx
    mov eax,2    ; now you have 2 in edx:eax
    mov ecx,38   ; 2^n, in this case 2^38 (any value x, 1 <= x <= 63, is valid).

x1: dec ecx      ; decrease ecx by 1
    jz ready     ; if it's 2^1, we are ready.

    shl eax,1    ; shift eax left through carry flag (CF) (overflow makes edx:eax zero)
    rcl edx,1    ; rotate edx through carry flag (CF) left
    jmp x1

ready:            ; edx:eax contains now 2^38.

Example: 2
Code: [Select]
  mov     ecx,38          ; input (exponent) in ecx. 2^n, in this case 2^38.
                            ; (any value x, 0 <= x <= 63, is valid).
; the code begins here.

    xor     eax,eax
    xor     edx,edx         ; edx:eax is now prepared.

    cmp     cl,64           ; if (cl >= 64),
    setb    al              ; then set eax to 0, else set eax to 1.
    jae     ready           ; this is to handle cl >= 64.

; now we have 0 <= cl <= 63

    sub     ecx,1
    setnc   al              ; if (count == 0) then eax = 0, else eax = 1.
    lea     eax,[eax+1]     ; eax = eax + 1. does not modify any flags.
    jna     ready           ; 2^0 is 1, 2^1 = 2, those are ready now.
    mov     ebx,ecx         ; copy ecx to ebx
    cmp     cl,32           ; if (cl >= 32)
    jb      low_5_bits
    mov     cl,31           ; then shift first 31 bits to the left.
    shld    edx,eax,cl
    shl     eax,cl          ; now shifted 31 bits to the left.
    lea     ecx,[ebx-31]    ; cl = bl - 31

low_5_bits:
    shld    edx,eax,cl
    shl     eax,cl

ready:

 What I gather is that bit shifting is taking place to make values small enough to fit into registers. Correct?

The following below is what I can make out from reading the codes.

Example 1: Utilizes Jumps based on Conditionals

(1) First xor is used to set the registers to 0
(2) 2 is then moved into the eax register
(3) 38 is then moved into the ecx register
(4) The value in ecx is decreased by 1 and the it loops until a certain value is reached, How would verify that the answer is and print it to a win32 window. (This is where I am confused at. When i run the code I get values in the registers that are not 274,877,906,944) so i assume that i need to perform another step to get the expected value.


Example 2: Doesn't utilize jumps, I gather that its making use of byte shifting to alter values which is a concept I understand through reading about it. (I picked x86 assembly as the first programming language to learn ,painful; but I do not regret it.)

(1) I cant explain code much farther, except the fact that it is using a different method or algorithm?

Can someone give a an explanation as to how the code would arrive at 274,877,906,944 through bit shifting, it would help me progress.

This may be off-topic, but do stacks operate in a similar fashion that RPN calculators operate (Ignore if you want).
Forgive any grammar/typos

felipe

  • Member
  • ***
  • Posts: 378
  • assemble the unassembled.
Re: Handling exponents and printing large numbers to console or win32
« Reply #1 on: July 13, 2017, 03:33:24 PM »


Example 1:
Code: [Select]
xor edx,edx
    mov eax,2    ; now you have 2 in edx:eax
    mov ecx,38   ; 2^n, in this case 2^38 (any value x, 1 <= x <= 63, is valid).

x1: dec ecx      ; decrease ecx by 1
    jz ready     ; if it's 2^1, we are ready.

    shl eax,1    ; shift eax left through carry flag (CF) (overflow makes edx:eax zero)
    rcl edx,1    ; rotate edx through carry flag (CF) left
    jmp x1

ready:            ; edx:eax contains now 2^38.



The following below is what I can make out from reading the codes.

Example 1: Utilizes Jumps based on Conditionals

(1) First xor is used to set the registers to 0
(2) 2 is then moved into the eax register
(3) 38 is then moved into the ecx register
(4) The value in ecx is decreased by 1 and the it loops until a certain value is reached, How would verify that the answer is and print it to a win32 window. (This is where I am confused at. When i run the code I get values in the registers that are not 274,877,906,944) so i assume that i need to perform another step to get the expected value.



Can someone give a an explanation as to how the code would arrive at 274,877,906,944 through bit shifting, it would help me progress.



Well, first of all welcome to the forum.  :t
Second:  for the fourth point, you need to convert the result in edx:eax  register pairs, into ascii values to see this value in a decimal fashion. The algo is correct, but the register hold the value in binary. Third is: The code would simply multiply eax by 2 (in each loop), because is that what you do when you perform something like this: 2^x (that is 2*2*2....x times). By rotating the contents in edx trough the carry flag, we insure that every bit that go out from eax comes into edx, moving forward (to the most significant digits of the number) as the operation dictates (x times). Because the whole number is a binary number, every bit count. Fourth: Well, my english is not the most brilliant and my explanation maybe not so clear. You should keep studying. Fifth: In the second example there's an instruction that i don't know (i'm kind of new to the 32 bit assembly programming) so i won't tell you something about it.  :bgrin:
Felipe.

aw27

  • Member
  • ****
  • Posts: 863
  • Let's Make ASM Great Again!
Re: Handling exponents and printing large numbers to console or win32
« Reply #2 on: July 13, 2017, 03:37:54 PM »
How would verify that the answer is and print it to a win32 window.

Just print it.

Code: [Select]
.386
.model flat, stdcall
option casemap :none 

includelib \masm32\lib\msvcrt.lib
sprintf proto C :vararg
includelib \masm32\lib\user32.lib
MessageBoxA proto :ptr,:ptr,:ptr,:DWORD
includelib \masm32\lib\kernel32.lib
ExitProcess proto :dword

.data
   format db "%lld", 13, 10, 0
   _title db "Result",13,10,0
   
.code

main PROC
LOCAL szBuf[9]:byte

xor edx,edx
mov eax,2    ; now you have 2 in edx:eax
mov ecx,38   ; 2^n, in this case 2^38 (any value x, 1 <= x <= 63, is valid).

x1:
dec ecx      ; decrease ecx by 1
jz ready     ; if it's 2^1, we are ready.

shl eax,1    ; shift eax left through carry flag (CF) (overflow makes edx:eax zero)
rcl edx,1    ; rotate edx through carry flag (CF) left
jmp x1

ready: 
invoke sprintf, addr szBuf, offset format, eax, edx
invoke MessageBoxA, 0, addr szBuf, offset _title, 0
invoke ExitProcess, 0
main ENDP
END main
« Last Edit: July 13, 2017, 04:50:25 PM by aw27 »

jj2007

  • Member
  • *****
  • Posts: 7764
  • Assembler is fun ;-)
    • MasmBasic
Re: Handling exponents and printing large numbers to console or win32
« Reply #3 on: July 13, 2017, 05:30:42 PM »
In MASM, there are quite a number of library routines available for printing large numbers.

include \masm32\MasmBasic\MasmBasic.inc         ; download
  Init
  Print Str$("The value is %i\n", ExpXY(2, 38))
EndOfCode


The value is 274877906944

mineiro

  • Member
  • ***
  • Posts: 365
Re: Handling exponents and printing large numbers to console or win32
« Reply #4 on: July 14, 2017, 12:47:23 AM »
hello Chris., welcome
Quote
Can someone give a an explanation as to how the code would arrive at 274,877,906,944 through bit shifting, it would help me progress.
How much is 2+2?, let's do in binary base:
 10+ (one zero) +
 10= (one zero)
---- = (carry go to left)
100  (one zero zero)
Can you see that if we sum a binary number with itself we are rotating that number to left by one digit and inserting 'zero''s at right side?

Processors work with binary, so rotating to left side one digit means multiply by 2, two digits means multiply by 4 and go on.
If rotating to left we are multiplying so rotating to right we can divide.

Your second example is like this, suppose that our registers can hold only 2 bits (instead of 32 bits).
How we can do calculus with numbers that the result is above 2 bits? We need add the 'carry bit' of that sum to left bits group.
__ 10+
__ 10=
------
01 00
That's why author of 2nd example is using "shld" instruction, like a train and one wagon, when the train goes to left one step, wagon goes to left one position too.
__ 10
shld above number (train and wagon) by one step is equal to
_1 00
And this way we don't need deal with 'carry' that happens on "junction" of both binary groups (registers).
But shld really rotate only destination while source  stay untouchable (do not rotate), this is why we need a "shl" to rotate that source if need after shld instruction use.

To print that number we need convert that binary number to ascii representation, well, to symbols (letters,numbers,...) that we can recognize.
So, number zero inside computer is not "number zero" that you see on screen, they are different. "Number zero" pressed on keyboard is not number zero inside computer.

---edit--- shld info
« Last Edit: July 14, 2017, 01:48:54 AM by mineiro »
I'd rather be this ambulant metamorphosis than to have that old opinion about everything