flat assembler
Message board for the users of flat assembler.

 Index > Heap > How large does it go?
Author
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
Let f(m,n) = 2m, n=0; (λx. f(x, n-1))^m (m)
how does it go up when m,n increase
Code:
```typedef unsigned large int uint;
uint f(uint m, uint n) {
if (n==0) {
return 2 * m;
} else {
for (uint i=m; i--; ) {
m = f(m, n-1);
}
return m;
}
}
```

Last edited by l4m2 on 29 Nov 2016, 16:52; edited 1 time in total
29 Nov 2016, 11:45
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 17278
revolution
Can you show what the notation means? λx = ? (m) = ?

If you have some equivalent assembly code to show what is all means then even better.
29 Nov 2016, 11:50
YONG

Joined: 16 Mar 2005
Posts: 8000
Location: 22° 15' N | 114° 10' E
YONG
Some sort of recursive function, I guess.

f(m, 0) = 2m

The dot after λx probably means " * ".

Needs clarification, anyway.

29 Nov 2016, 12:42
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
Just in C/C++
29 Nov 2016, 12:49
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
Code:
```f(0,0)=0      f(1,0)=2      f(2,0)=4      f(3,0)=6
f(0,1)=0      f(1,1)=2      f(2,1)=8      f(3,1)=24
f(0,2)=0      f(1,2)=2      f(2,2)=2048   f(3,2)=3*2^16777267
f(0,3)=0      f(1,3)=2      f(2,3)=∏(2^2^...[i 2^'s]^2048)^C(2048,i) > 2^^2048    ```
29 Nov 2016, 17:50
bitRAKE

Joined: 21 Jul 2003
Posts: 2915
Location: [RSP+8*5]
bitRAKE
Code:
```; RAX = m
; RCX = n
f:  sub rcx,1           ; n-1
jnc .lupe
shl rax,1           ; m*2
retn
.lupe:
push rax            ; preserve loop counter
.p:
call f ; m=f(m,n-1)
sub qword [rsp],1
jnz .p
retn    ```
RAX needs to be replaced by a big integer fairly quickly.

If (n) is one then the shift is (m).
For example, notice how:

f(2,2) = f(f(2,1),1) = 8 SHL 8 = (2 SHL 2) SHL (2 SHL 2); and

f(3,2) = f(f(f(3,1),1),1) = [(3 SHL 3) SHL (3 SHL 3)] SHL [(3 SHL 3) SHL (3 SHL 3)].

f(m,0) = 2m
f(m,n) = f^m(m,n-1) ; i.e. f(f(f(f(...f(m,n-1)...,n-1),n-1),n-1),n-1)

Mathematica calls this Nest[], and it call be performed with any function.

;--------

f(m,n) = m * 2^g(m,n) :

It might be more useful to just track the shift count, and multiply by (m) if the same (f) is needed. It still grows beyond numerical representation very fast.

g(m,0) = 1
g(m,1) = m
g(m,n) = ?

_________________
30 Nov 2016, 04:46
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
Quote:

f(m,n) = f^m(m,n-1) ; i.e. f(f(f(f(...f(m,n-1)...,n-1),n-1),n-1),n-1)

So is f^2(m,n) f(f(m,n),n) or f(m,f(m,n))? To avoid mixing I used lambda expression to mean the exact meaning, only lead to treating the dot as multiply.
30 Nov 2016, 06:17
l4m2

Joined: 15 Jan 2015
Posts: 648
l4m2
Seems it doesn't go so high --- just near m[n]m
01 Dec 2016, 16:26
 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

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