flat assembler
Message board for the users of flat assembler.
 Home   FAQ   Search   Register 
 Profile   Log in to check your private messages   Log in 
flat assembler > Heap > What is the best pie you can get with 9 digits?

Goto page Previous  1, 2, 3 ... 25, 26, 27, 28  Next
Author
Thread Post new topic Reply to topic
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 6193
Location: Kraków, Poland

YONG wrote:
So, please also try:

{1, 4, 5, 6, 7, 9},
{1, 3, 5, 7, 8, 9},
{1, 2, 3, 5, 7, 9}, and
{1, 2, 3, 4, 5, 7}

for 924269.

I have not run full searches here but did a quick peeks at initial results for some of the sets and the best one I saw is:

Code:
[RPN13 5 9 8 / ^ ^ 7 / = 13^(5^(9/8))/7 = 924271.83467746343...

It has been found quite early in the scan, so there might still be better ones out there. But I think that we really need a native implementation to make these searches in reasonable time.
Post 06 Jan 2017, 12:21
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2621
Location: dank orb

YONG wrote:
In (278^4+-1)/59^6+3, there is no need to write "+-1". Just write "-1".

The expression ( 6 / 8 )^5 * (3/9)^1 * (7/4)^2 gives 0.24224853515. Something is wrong with your program.

Wink

I wrote +- because there are two solutions with five significant digits +1 and -1.

The other error is clerical in nature, human. Although my program works, it's output needs massaging as I didn't spend any time on that part of it. Also, that machine is not connected to any sort of network, so did a screen scrap with my tired eyes, lol.

Also, I've been unable to find anything interesting along sub-branches you've suggested.

_________________
Brevity is the source of all errors. ⠉⠕⠙⠑ Code wins arguments.
Post 09 Jan 2017, 07:37
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E

Tomasz Grysztar wrote:
[RPN] 13 5 9 8 / ^ ^ 7 / = 13^( 5^( 9 / 8 )) / 7 = 924271.83467746343...

924271 is not close enough. Sad
Post 09 Jan 2017, 09:25
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E

bitRAKE wrote:
I wrote +- because there are two solutions with five significant digits +1 and -1.

I see. Both solutions are correct to 3 decimal places.

(278^4+1)/59^6+3 = 3.141601258 ...
(278^4-1)/59^6+3 = 3.141601258 ...


In fact, I believe we may try all possibilities of the expression

(a/b)^c * (d/e)^f * (g/h)^i

to see if there are any good approximations.



bitRAKE wrote:
I've been unable to find anything interesting along sub-branches you've suggested.

Luck is not on our side! Sad


Wink
Post 09 Jan 2017, 09:37
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2621
Location: dank orb

YONG wrote:
In fact, I believe we may try all possibilities of the expression

(a/b)^c * (d/e)^f * (g/h)^i

to see if there are any good approximations.

That's a pattern I've exhausted, and posted the best solution. Wink

Think I'll just convert Tomasz' code to x86 and see how far it goes.

_________________
Brevity is the source of all errors. ⠉⠕⠙⠑ Code wins arguments.
Post 25 Jan 2017, 05:00
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E

bitRAKE wrote:
Think I'll just convert Tomasz' code to x86 and see how far it goes.

That is great news! Good luck!

Wink
Post 25 Jan 2017, 05:12
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2621
Location: dank orb
[ (9/8) + 7/((6*5)/4)^3 + 2 ]^1 = 3.14159(259)

Still debugging code, but looks good.
Post 06 Feb 2017, 10:31
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E
Brilliant!

So, the best answers as of now are still correct to 6 decimal places:

bitRAKE: [ ( 9 / 8 ) + 7/((6*5)/4)^3 + 2 ]^1 = 3.14159259259 ...
T.G.: (2+6*9/743)*8^(1/5) = 3.14159288348 ...
YONG: 3^1 + (4^2)/((9+5)*8 + 7 - 6) = 3.14159292035 ...

Wink
Post 06 Feb 2017, 10:46
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2621
Location: dank orb
Some interesting results:

Code:
; Trying to approximate PI: 3.141592653589793238462643383279503...
;
; Returned equations:
;
; 6:  3 26 1 4 - 5 / ^ + = 3+26^((1-4)/5)                       (complete)
;   = 3.1415 84591
; 7:  5 3 6 4 + 2 ^ 71 / - / =  5/( 3 - (6+4)^2/71 )            (complete)
;   = 3.141592 92035
; 8:  631 2 7 5 / 4 / 8 - ^ * = 631*2^(7/5/4 - 8)
;   = 3.141592 79624

Only one thru seven is needed to produce an approximation to six digits. Eight hasn't finished, yet.

Regarding the code, I think the dispatcher can be improved greatly - allowing nine to be completed in less than a day. I'm fairly confident most the bugs are gone.

Code:
FORMAT PE64 CONSOLE 6.0 AT $10000 ON 'NUL'
include '..\win64-simple.finc'
SECTION '' CODE EXECUTABLE READABLE WRITEABLE


; Some Global Structures/Constants: ;
; --------------------------------- ;
__N equ 9 ; global digit count
__O equ 5 ; global number of operations

    align 64
label __digits:byte
                        rept __N i:1 {db i}
; these digits are manipulated to transverse all possible combinations

    align 64
__numbers               rd 2   ; how many in use?
__number_list           rq __N ; maximum possible
; for each ordered set of digits, every possible partitioning is generated

    align 64
__variation             rq 1
; [length(numbers) - 1]^5 possible operator combinations, count them down
__distribution          rb __N+2
; track how operators are distributed amongst the numbers
; entry [0] must always be zero, to output a number without an operation


align 16
__Epsilon dq 0.001 ; best distance to goal


align 64,nop
; Can not modify global structures in use, or registers
RPN_Print.error:
        int3
RPN_Print:
        push rax rcx rdx rbx rsi rdi r8
        mov ecx,[__numbers]
        jrcxz .error
        push [__variation]
        lea rsi,[__distribution]
        lea rdi,[__buffer]

 .termjrcxz @F
        mov rax,[__number_list+rcx*8-8]
        sub ecx,1
        call .number
    @@lodsb
        test al,al
        jz .term
        xchg ebx,eax
 .ops:  pop rax
        xor edx,edx
        div [OPERATIONS]
        push rax
        mov ah,' '
        mov al,[.ASCII+rdx]
        stosw
        sub bl,1
        jnz .ops

        cmp byte [rsi],$FF
        jnz .term
        pop rax

        mov ax,13+(10*256; cr lf
        stosw
        ;------------------------------
        enter 32+16,0
        and rsp,-16
        push STD_OUTPUT_HANDLE
        pop rcx
        dll [kernel32 GetStdHandle]
        mov r8,rdi
        xchg rcx,rax
        lea rdx,[__buffer]
        sub r8,rdx ; bytes
        lea r9,[rsp+40; lpNumberOfBytesWritten
        and qword [rsp+32],0 ; lpOverlapped
        dll [kernel32 WriteFile]
        leave

        pop r8 rdi rsi rbx rdx rcx rax
        retn

 .number; RAX to ASCII at RDI, advance string pointer
      push 0
  @@xor edx,edx
      div [.ten]
      add edx,'0'
      push rdx
      test rax,rax
      jnz @B

  @@pop rax
      stosb
      test al,al
      jnz @B
      mov byte [rdi-1],' '
      retn

.ASCII db "+-*/^"
align 8
.ten dq 10




align 64
Dispatcher_Exception:
        virtual at rcx
          .eps EXCEPTION_POINTERS
        end virtual
        mov rax,[.eps.ContextRecord]
        virtual at rax
          .cntx CONTEXT
        end virtual

        ; WARNING: ignores reason for exception

        ; if RIP is within the leaves of dispatcher then skip this
        ; distribution of operators as INVALID, most likely /0.
        cmp [.cntx.Rip],Dispatcher.__TAIL__ ;#32#
        jnc .not_ours
        cmp [.cntx.Rip],Dispatcher.__HEAD__ ;#32#
        jnc .got_one
 .not_ours:
        mov eax,EXCEPTION_CONTINUE_SEARCH
        retn
 .got_one:
        mov [.cntx.Rip],Dispatcher.bypass ; #32#
        mov eax,EXCEPTION_CONTINUE_EXECUTION
        retn




align 64,nop
Dispatcher:
    cmp ecx,2
    jc .end
    mov [.RSP_WALL],rsp
    push [.variations+(rcx-1)*8]
    pop [__variation]

 .variation:
    mov ecx,[__numbers]
;    mov [__distribution],$00 ; first non-operation (always)
    mov [__distribution+rcx],$FF ; terminator
    jmp .init_distribution

 .bypass; error happened, try to recover for next distribution
    mov rsp,[.RSP_WALL]
    fninit

 .next_distribution:
        lea rdi,[__distribution+1]
        mov ecx,[__numbers]
        xor eax,eax
        repz scasb              ; find non-zero
        add byte [rdi],1        ; put FF bytes at end to terminate variation
        jc .var_end
        movzx ecx,byte[rdi-1]
        mov [rdi-1],al
 .init_distribution:
        sub ecx,1
        lea rdi,[__distribution+1]
        mov al,1
        rep stosb
;-------
        mov ecx,[__numbers]
        lea rsi,[__distribution]
        lea rdi,[__buffer]
        push [__variation]

 .termjrcxz @F
        fild [__number_list+rcx*8-8]
        fstp qword [rdi]
        add rdi,8
        sub ecx,1

    @@lodsb
        test al,al
        jz .term
        xchg ebx,eax
 .ops:  pop rax
        xor edx,edx
        div [OPERATIONS]
        push rax

        fld qword [rdi-16]
        fld qword [rdi-8]
        call [.table+rdx*8]
        fstp qword [rdi-16]
        sub rdi,8

        sub bl,1
        jnz .ops

        cmp byte [rsi],$FF
        jnz .term
        pop rax

;int3
        fld qword [rdi-8; should be [__buffer]
        fldpi
        fsubp
        fabs
        fld [__Epsilon]
        fcomip st0,st1
        jna .not_better
        fst [__Epsilon]
        call RPN_Print
 .not_better:
        fstp st
        jmp .next_distribution
 .var_end:
        sub [__variation],1
        jnc .variation
 .end:  retn


 .__HEAD__:
 .Add:  faddp
        retn
 .Sub:  fsubp
        retn
 .Mul:  fmulp
        retn
 .Div:  fdivp           ; divide by zero needs to be captured by exception
        retn            ; handler and result aborted
 .Pow:  fxch
        fxam            ; handle negative st0
        fnstsw ax       ;
        fabs            ;
        fyl2x
        fld st0
        frndint
        fsub st1,st0
        fxch
        f2xm1
        fld1
        faddp
        fscale
        fstp st1
        test ah,001b
        jz .Pow.positive
        fld1 ; reciprocal
        fdivrp
 .Pow.positive:
        retn
 .__TAIL__:

align 64,db 0
 .table dq .Add,.Sub,.Mul,.Div,.Pow       ; pointer array of operations
 .RSP_WALL rq 1

 ; constant array for a given number operations and terms
 .i = 1
 label .variations:qword
 rept __N { dq .i - 1
 .i = .i * __O }



align 64,nop
Partitions:
    mov rax,(1 shl (__N-1)) - 1
    mov [.bits],rax
 .part:
    mov ebx,__N-1
    xor ecx,ecx
    movzx eax,[__digits+rbx]
    jmp .get
 .more:
    imul rax,rax,10
    add rax,rdx
 .get:
    sub ebx,1
    jc .store
    movzx edx,[__digits+rbx]
    bt dword [.bits],ebx
    jnc .more
 .store:
    mov [__number_list+rcx*8],rax
    add ecx,1
    xchg eax,edx
    test ebx,ebx
    jns .get
    mov [__numbers],ecx
    call Dispatcher
    sub [.bits],1
    jnc .part
    retn

.bits rq 1




MainENTRY $;##################################################################

    and rsp,-64

; Dispatcher needs to be protected from errors
    push -1
    pop rcx
    lea rdx,[Dispatcher_Exception]
    dll [kernel32 AddVectoredExceptionHandler]
    mov [hVException],rax
    fninit

; non-recursive Heap's algorithm

    ; clear .C array to zeroes
    jmp .entry
    align 64
 .odd; swap items
    movzx edx,[.C+rax]
    mov cl,[__digits+rdx]
    mov [__digits+rdx],ch
 .odd_tail:
    mov [__digits+rax],cl
    add [.C+rax],1
 .entry:
    call Partitions
    xor eax,eax         ; set i
 .i_le:
    mov [.C+rax],0
    add al,1
 .while:                ; i < n
    cmp al,__N
    jnc .end
    cmp [.C+rax],al     ; if c[i] < i
    jnc .i_le
    mov ch,[__digits+rax]
    test al,1
    jnz .odd            ; 50%
    mov cl,[__digits]
    mov [__digits],ch
    jmp .odd_tail
 .end:

; little clean-up

    mov rcx,[hVException]
    dll [kernel32 RemoveVectoredExceptionHandler]

        xor ecx,ecx
        dll [kernel32 ExitProcess]
        int3

align 64,db 0
.C rb __N

align 16,db 0
OPERATIONS dq __O
hVException rq 1


imports;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


align 64
__buffer rb 4096


_________________
Brevity is the source of all errors. ⠉⠕⠙⠑ Code wins arguments.
Post 07 Feb 2017, 05:22
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E

bitRAKE wrote:
Regarding the code, I think the dispatcher can be improved greatly - allowing nine to be completed in less than a day. I'm fairly confident most the bugs are gone.

Any chance that I could get the Linux version of the code? Rolling Eyes

I am using GalliumOS right now.

Wink
Post 07 Feb 2017, 07:27
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14483
Location: Can't remember

YONG wrote:
Any chance that I could get the Linux version of the code?

It would by easy to convert. But you would have to actually write some code Shocked

Razz
Post 07 Feb 2017, 08:28
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2621
Location: dank orb
Seven digits of percision is possible with [1-8] equation. Smile

( 2*8 )/(4^(73/56) - 1)

It would be unusual if [1-9] equation could not improve on this result.
Post 07 Feb 2017, 13:52
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2621
Location: dank orb

YONG wrote:
Any chance that I could get the Linux version of the code?

The OS is only used to output a string of length (could be changed to null terminated with single instruction). Also, there is an exception handler (like try/catch in other languages). All other code is non ABI specific.

In fact, Heap's algorithm has the nice property of all state being in the update array. notice how only RAX needs to be cleared after the CALL. The Partitions routine was designed in a similar manner - easing pressure on Dispatcher interface. I have more general (thread-safe) versions of these routines as well.

_________________
Brevity is the source of all errors. ⠉⠕⠙⠑ Code wins arguments.
Post 07 Feb 2017, 14:22
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E

bitRAKE wrote:
Seven digits of percision is possible with [1-8] equation. Smile

( 2*8 )/(4^(73/56) - 1)

That expression does not count because the digit "9" is missing. Sorry for that.

In fact, my earlier attempt that requires one more digit can also give 7 decimal places:

(6^3 * 4279 + 5)^(1/(8+4)) = 924269^(1/12) = 3.14159260217 ...

We should stick to the rules!

Wink
Post 08 Feb 2017, 03:08
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E

bitRAKE wrote:

YONG wrote:
Any chance that I could get the Linux version of the code?

The OS is only used to output a string of length (could be changed to null terminated with single instruction). Also, there is an exception handler (like try/catch in other languages). All other code is non ABI specific.

In fact, Heap's algorithm has the nice property of all state being in the update array. notice how only RAX needs to be cleared after the CALL. The Partitions routine was designed in a similar manner - easing pressure on Dispatcher interface. I have more general (thread-safe) versions of these routines as well.

Thanks for the info. I don't have time to do coding right now. Maybe I'll try coding the Linux version later.

Wink
Post 08 Feb 2017, 03:10
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E
So, the best answers as of now are still correct to 6 decimal places:

bitRAKE: [ ( 9 / 8 ) + 7/((6*5)/4)^3 + 2 ]^1 = 3.14159259259 ...
T.G.: (2+6*9/743)*8^(1/5) = 3.14159288348 ...
YONG: 3^1 + (4^2)/((9+5)*8 + 7 - 6) = 3.14159292035 ...

Wink
Post 08 Feb 2017, 03:15
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 14483
Location: Can't remember
In terms of ratio bitRAKE is the closest.
Post 08 Feb 2017, 03:26
View user's profile Send private message Visit poster's website Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 6290
Location: ˛                              ⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣ Posts: 6699
the actual pi is what divide by what?
Post 08 Feb 2017, 04:48
View user's profile Send private message Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E

sleepsleep wrote:
the actual pi is what divide by what?

The circumference of a circle divided by its diameter.

Wink
Post 08 Feb 2017, 05:03
View user's profile Send private message Visit poster's website Reply with quote
YONG



Joined: 16 Mar 2005
Posts: 6712
Location: 22° 15' N | 114° 10' E

revolution wrote:
In terms of ratio bitRAKE is the closest.

Correct. That's why his expression currently tops the list of best answers.

Wink
Post 08 Feb 2017, 05:04
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3 ... 25, 26, 27, 28  Next

< 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 can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001-2005 phpBB Group.

Main index   Download   Documentation   Examples   Message board
Copyright © 2004-2016, Tomasz Grysztar.