flat assembler
Message board for the users of flat assembler.

Index > Main > The sum of digits 2^100000?

Author
Thread Post new topic Reply to topic
wht36



Joined: 18 Sep 2005
Posts: 106
wht36 12 Oct 2011, 15:56
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^100000?

The program below, using bitRAKE's algorithm (http://projecteuler.net/thread=16), returns 0. (Correct answer is at: http://oeis.org/A101429 )

What did I do wrong?

Code:
format pe console
include 'win32ax.inc'
section '.idata' import data readable writeable
library msvcrt, 'msvcrt.dll', kernel32, 'kernel32.dll'
import msvcrt, printf, 'printf'
import kernel32, ExitProcess,'ExitProcess'     

section '.code' code readable executable
entry $
POWER = 100000

      ; set up number in binary
   mov edi,number
      mov ebp, edi
        sub eax,eax
 mov ecx,(POWER+31)/32
       rep stosd
   mov eax, POWER
      bts [ebp], eax

  ; convert to decimal to sum digits
  mov edi, (POWER+31)/32 - 1
  mov ecx, 10
 xor ebx, ebx ; sum

_0:       mov esi, edi ; dwords to convert
    xor edx, edx
@@: mov eax, [ebp+esi*4]
        div ecx
     mov [ebp+esi*4], eax
        dec esi
     jns @B

  add ebx, edx

    cmp DWORD [ebp+edi*4], 0
    jne _0
      dec edi
     jns _0

  mov eax,ebx
 sub edx,edx

   cinvoke printf, "%d", eax
   invoke ExitProcess, 0

.data
sum: rd 1
number: rd (POWER+31)/32    
Post 12 Oct 2011, 15:56
View user's profile Send private message Reply with quote
Goplat



Joined: 15 Sep 2006
Posts: 181
Goplat 12 Oct 2011, 17:57
Quote:
mov ecx,(POWER+31)/32
rep stosd
mov eax, POWER
bts [ebp], eax

; convert to decimal to sum digits
mov edi, (POWER+31)/32 - 1

...
number: rd (POWER+31)/32

Off-by-one bugs. Remember, you need POWER+1 bits to represent 2^POWER. So ecx, and the size of number, should be POWER/32+1 dwords, and edi should be just POWER/32.
Post 12 Oct 2011, 17:57
View user's profile Send private message Reply with quote
wht36



Joined: 18 Sep 2005
Posts: 106
wht36 13 Oct 2011, 05:11
Brilliant! It works! Thank you so very much!!

Here's a 16bit version for DOS people.
Code:
;2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
;
;What is the sum of the digits of the number 2^10000?

org 100h

POWER = 10000

   ; set up number in binary
   mov di, Number
      mov bp, di              ;we need POWER+1 bits to represent 2^POWER
  mov cx, POWER/16        ;CX = number of words required -1
   sub ax,ax
   rep stosw
   mov word [di], 1 shl (POWER mod 16)
 sub di,bp               ;DI -> relative offset of highest word

       ; convert to decimal to sum digits
  mov cx, 10              ; base
      xor bx, bx              ; sum

_0:    mov si, di              ; SI = DI = highest word
    xor dx, dx
@@:   mov ax, [bp+si]
     div cx
      mov [bp+si], ax         ; store quotient
    dec si
      dec si                  ; next word
 jns @B

  add bx, dx

      cmp word [bp+di], 0     ; continue division until highest word is zero
      jne _0
      dec di
      dec di                  ; one word less
     jns _0

  mov ax,bx
putd:  mov cx,10
.div:  sub dx,dx       ; clear DX
  div cx          ; divide AX by BX
   or ax,ax
    jz .asc         ; if quotient is zero goto undo
     push dx         ; store remainder
   call .div       ; divide again
      pop dx          ; restore remainder
.asc:        add dl,'0'    ; and convert it to ASCII characters
putc:       mov ah,2
    int 21h
exit:    ret

Number:
    
Post 13 Oct 2011, 05:11
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.