flat assembler
Message board for the users of flat assembler.

Index > Heap > How large does it go?

Author
Thread Post new topic Reply to topic
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
Post 29 Nov 2016, 11:45
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17278
Location: In your JS exploiting you and your system
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. Smile
Post 29 Nov 2016, 11:50
View user's profile Send private message Visit poster's website Reply with quote
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.

Wink
Post 29 Nov 2016, 12:42
View user's profile Send private message Visit poster's website Reply with quote
l4m2



Joined: 15 Jan 2015
Posts: 648
l4m2
Just in C/C++
Post 29 Nov 2016, 12:49
View user's profile Send private message Reply with quote
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    
Post 29 Nov 2016, 17:50
View user's profile Send private message Reply with quote
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
    add rcx,1           ; preserve (n)
    retn
.lupe:
    push rax            ; preserve loop counter
.p:
    call f ; m=f(m,n-1)
    sub qword [rsp],1
    jnz .p
    add rsp,8
    add rcx,1           ; preserve (n)
    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) = ?

_________________
¯\(°_o)/¯ unlicense.org
Post 30 Nov 2016, 04:46
View user's profile Send private message Visit poster's website Reply with quote
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.
Post 30 Nov 2016, 06:17
View user's profile Send private message Reply with quote
l4m2



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


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.