flat assembler
Message board for the users of flat assembler.

 Index > Heap > What is the best pie you can get with 9 digits? Goto page Previous  1, 2, 3 ... 25, 26, 27, 28, 29  Next
Author
Tomasz Grysztar
Assembly Artist

Joined: 16 Jun 2003
Posts: 7719
Location: Kraków, Poland
Tomasz Grysztar
YONG wrote:

{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:
`[RPN] 13 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.
06 Jan 2017, 12:21
bitRAKE

Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
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.

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.

_________________
09 Jan 2017, 07:37
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
Tomasz Grysztar wrote:
[RPN] 13 5 9 8 / ^ ^ 7 / = 13^( 5^( 9 / 8 )) / 7 = 924271.83467746343...
924271 is not close enough.
09 Jan 2017, 09:25
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
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!

09 Jan 2017, 09:37
bitRAKE

Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
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.

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

_________________
25 Jan 2017, 05:00
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
bitRAKE wrote:
Think I'll just convert Tomasz' code to x86 and see how far it goes.
That is great news! Good luck!

25 Jan 2017, 05:12
bitRAKE

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

Still debugging code, but looks good.
06 Feb 2017, 10:31
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
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 ...

06 Feb 2017, 10:46
bitRAKE

Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
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]

.term: jrcxz @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]
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
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]

.term: jrcxz @F
fild [__number_list+rcx*8-8]
fstp qword [rdi]
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

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
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
.get:
sub ebx,1
jc .store
movzx edx,[__digits+rbx]
bt dword [.bits],ebx
jnc .more
.store:
mov [__number_list+rcx*8],rax
xchg eax,edx
test ebx,ebx
jns .get
mov [__numbers],ecx
call Dispatcher
sub [.bits],1
jnc .part
retn

.bits rq 1

Main: ENTRY \$;##################################################################

and rsp,-64

; Dispatcher needs to be protected from errors
push -1
pop rcx
lea rdx,[Dispatcher_Exception]
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
.entry:
call Partitions
xor eax,eax         ; set i
.i_le:
mov [.C+rax],0
.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    ```

_________________
07 Feb 2017, 05:22
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
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?

I am using GalliumOS right now.

07 Feb 2017, 07:27
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
revolution
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

07 Feb 2017, 08:28
bitRAKE

Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
Seven digits of percision is possible with [1-8] equation.

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

It would be unusual if [1-9] equation could not improve on this result.
07 Feb 2017, 13:52
bitRAKE

Joined: 21 Jul 2003
Posts: 2913
Location: [RSP+8*5]
bitRAKE
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.

_________________
07 Feb 2017, 14:22
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
bitRAKE wrote:
Seven digits of percision is possible with [1-8] equation.

( 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!

08 Feb 2017, 03:08
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
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.

08 Feb 2017, 03:10
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
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 ...

08 Feb 2017, 03:15
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17270
revolution
In terms of ratio bitRAKE is the closest.
08 Feb 2017, 03:26
sleepsleep

Joined: 05 Oct 2006
Posts: 8885
Location: ˛　　　　　　　　　　　　　　　　　　　　　　　　　　　　　⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
sleepsleep
the actual pi is what divide by what?
08 Feb 2017, 04:48
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
sleepsleep wrote:
the actual pi is what divide by what?
The circumference of a circle divided by its diameter.

08 Feb 2017, 05:03
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
revolution wrote:
In terms of ratio bitRAKE is the closest.
Correct. That's why his expression currently tops the list of best answers.

08 Feb 2017, 05:04
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area
Goto page Previous  1, 2, 3 ... 25, 26, 27, 28, 29  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou can attach files in this forumYou can download files in this forum