Re: Stack Space & Ackermann

[H. S. Teoh via Digitalmars-d-learn]

On Thu, Jan 05, 2017 at 04:50:19AM +, Era Scarecrow via Digitalmars-d-learn 
wrote:
> Well re-watched a video regarding the Ackermann function which is a
> heavily recursive code which may or may not ever give a result in our
> lifetimes.  However relying on the power of memoize I quickly find
> that when the program dies (from 5 minutes or so) nearly instantly
> (and only using 9Mb of memory).
> 
> long ack(long m, long n) {
> long ans;
> 
> if (m == 0) ans = n + 1;
> else if (n==0) ans = ack(m-1, 1);
> //else ans = ack(m-1, ack(m, n-1)); // original
> else ans = memoize!ack(m-1, memoize!ack(m, n-1));
> 
> return ans;
> }
> 
> This is only due to the limited stackframe space.
[...]

For heavily-recursive functions like this one, you *really* want to be
revising the algorithm so that it *doesn't* recurse on the runtime
stack.  Keep in mind that the Ackermann function was originally
conceived specifically to prove that a certain elementary class of
recursive functions (called "primitive recursive" functions) cannot
perform certain computations. Very roughly speaking, primitive recursive
functions are "well-behaved" with regard to recursion depth; so the
Ackermann function was basically *designed* to have very bad
(unrestricted) recursion depth such that no primitive recursive function
could possibly catch up to it. Translated to practical terms, this means
that your runtime stack is pretty much guaranteed to overflow except for
the most trivial values of the function.

The other problem with your code, as written, is that it will quickly
and easily overflow any fixed-width integer such as long here. For
example, ack(4,1) == 65533, but ack(4,2) is a value that requires 65536
bits to represent (i.e., an integer that's 1 KB in size), and ack(4,3)
is a value that requires ack(4,2) bits to represent, i.e., the number of
bits required is a number so huge that it itself requires 1KB to
represent. This far exceeds any memory capacity of any computer system
in existence today, and we haven't even gotten to ack(4,4) yet.

You might at least be able to get to ack(4,2) if you use BigInt instead
of long (though be prepared for incredibly huge running times before the
answer ever appears!), but even BigInt won't help you once you get to
ack(4,3) and beyond.  And don't even think about ack(5,n) for any value
of n greater than 0, because those values are so ridiculously huge you
need special notation just to be able to write them down at all.

Because of this, your code as written most definitely does *not* compute
the Ackermann function except for the smallest arguments, because once
ack(m, n-1) overflows long, it can only return the answer module
long.max, which will be much smaller than the actual value, so the
nested recursion ack(m-1, ack(n, m-1)) actually will compute a value far
smaller than what the real Ackermann function would (and it would run
much faster than the real Ackermann function).

Not to mention, the recursive definition of the Ackermann function is
really bad for actually computing its values in a computer, because it
makes a huge number of recursive calls just to compute something as
simple as + and * (essentially what ack(1,n) and ack(2,n) do). In a
practical implementation you'd probably want to special case these
arguments to use faster, non-recursive code paths.  Using memoize
alleviates the problem somewhat, but it could be improved more.

Nonetheless, even if you optimize said code paths, you still won't be
able to get any sane results for m>4 or anything beyond the first few
values for m=4. The Ackermann function is *supposed* to be
computationally intractible -- that's what it was designed for. :-P


T

-- 
Do not reason with the unreasonable; you lose by definition.

Re: Stack Space & Ackermann

[Era Scarecrow via Digitalmars-d-learn]

On Thursday, 5 January 2017 at 06:20:28 UTC, rikki cattermole 
wrote:

foreach(i; 0 .. 6)

No need for iota.


 I thought that particular slice/range was depreciated. Still the 
few k that are lost in the iota doesn't seem to make a difference 
when i run the code again.

Re: Stack Space & Ackermann

[rikki cattermole via Digitalmars-d-learn]

On 05/01/2017 7:03 PM, Era Scarecrow wrote:

On Thursday, 5 January 2017 at 04:53:23 UTC, rikki cattermole wrote:

Well, you could create a fiber[0].

Fibers allow you to set the stack size at runtime.

[0] http://dlang.org/phobos/core_thread.html#.Fiber.this


 Well that certainly does seem to do the trick. Unfortunately I didn't
get the next output because I ran out of memory to allocate/reallocate
over 2Gb :P

 I suppose with a 64bit compiling the program might run a bit longer and
succeed further (with 24Gigs of ram), however the sheer amount of memory
required will make this little exercise more or less a waste of time.

 Still that was an interesting way around the (stackframe) problem, one
I'll keep I mind (should i need it again).

void m() {
foreach(i; iota(6))
foreach(j; iota(6)) {
writefln("Ackerman (%d,%d) is : %d", i,j,ack(i,j));
}
}

int main(string[] args) {
Fiber composed = new Fiber(, 2<<28); //512MB
composed.call();

return 0;
}

results:

Ackerman (3,5) is : 253
Ackerman (4,0) is : 13
Ackerman (4,1) is : 65533

core.exception.OutOfMemoryError@src\core\exception.d(693): Memory
allocation failed



You're using more memory then need to:

foreach(i; 0 .. 6)

No need for iota.

Re: Stack Space & Ackermann

[Era Scarecrow via Digitalmars-d-learn]

On Thursday, 5 January 2017 at 04:53:23 UTC, rikki cattermole 
wrote:

Well, you could create a fiber[0].

Fibers allow you to set the stack size at runtime.

[0] http://dlang.org/phobos/core_thread.html#.Fiber.this


 Well that certainly does seem to do the trick. Unfortunately I 
didn't get the next output because I ran out of memory to 
allocate/reallocate over 2Gb :P


 I suppose with a 64bit compiling the program might run a bit 
longer and succeed further (with 24Gigs of ram), however the 
sheer amount of memory required will make this little exercise 
more or less a waste of time.


 Still that was an interesting way around the (stackframe) 
problem, one I'll keep I mind (should i need it again).


void m() {
foreach(i; iota(6))
foreach(j; iota(6)) {
writefln("Ackerman (%d,%d) is : %d", i,j,ack(i,j));
}
}

int main(string[] args) {
Fiber composed = new Fiber(, 2<<28); //512MB
composed.call();

return 0;
}

results:

Ackerman (3,5) is : 253
Ackerman (4,0) is : 13
Ackerman (4,1) is : 65533

core.exception.OutOfMemoryError@src\core\exception.d(693): Memory 
allocation failed

Re: Stack Space & Ackermann

[rikki cattermole via Digitalmars-d-learn]

On 05/01/2017 5:50 PM, Era Scarecrow wrote:

 Well re-watched a video regarding the Ackermann function which is a
heavily recursive code which may or may not ever give a result in our
lifetimes. However relying on the power of memoize I quickly find that
when the program dies (from 5 minutes or so) nearly instantly (and only
using 9Mb of memory).

long ack(long m, long n) {
long ans;

if (m == 0) ans = n + 1;
else if (n==0) ans = ack(m-1, 1);
//else ans = ack(m-1, ack(m, n-1)); // original
else ans = memoize!ack(m-1, memoize!ack(m, n-1));

return ans;
}

 This is only due to the limited stackframe space. Doing a search I find
that the amount of stack space is decided on when the EXE is being
compiled and in the EXE header but I'm not sure which one needs to be
update (supposedly it's either 250k or 1Mb is the default), although
neither help in this case, nor do the other binary tools as they don't
recognize the binary format of D's exe output files)

 Alternatively if there's a way to tell the compiler a hint (either in D
or in the compiling/linking flags) or the specific offset of which 32bit
entry is the stack reserved space, I could continue my little
unimportant side experiments.

 Suggestions? Comments?


Well, you could create a fiber[0].

Fibers allow you to set the stack size at runtime.

[0] http://dlang.org/phobos/core_thread.html#.Fiber.this

Stack Space & Ackermann

[Era Scarecrow via Digitalmars-d-learn]

 Well re-watched a video regarding the Ackermann function which 
is a heavily recursive code which may or may not ever give a 
result in our lifetimes. However relying on the power of memoize 
I quickly find that when the program dies (from 5 minutes or so) 
nearly instantly (and only using 9Mb of memory).


long ack(long m, long n) {
long ans;

if (m == 0) ans = n + 1;
else if (n==0) ans = ack(m-1, 1);
//else ans = ack(m-1, ack(m, n-1)); // original
else ans = memoize!ack(m-1, memoize!ack(m, n-1));

return ans;
}

 This is only due to the limited stackframe space. Doing a search 
I find that the amount of stack space is decided on when the EXE 
is being compiled and in the EXE header but I'm not sure which 
one needs to be update (supposedly it's either 250k or 1Mb is the 
default), although neither help in this case, nor do the other 
binary tools as they don't recognize the binary format of D's exe 
output files)


 Alternatively if there's a way to tell the compiler a hint 
(either in D or in the compiling/linking flags) or the specific 
offset of which 32bit entry is the stack reserved space, I could 
continue my little unimportant side experiments.


 Suggestions? Comments?

Re: Parsing a UTF-16LE file line by line, BUG?

[Daniel Kozák via Digitalmars-d-learn]

Nestor via Digitalmars-d-learn  
napsal St, led 4, 2017 v 8∶20 :

On Wednesday, 4 January 2017 at 18:48:59 UTC, Daniel Kozák wrote:
Ok, I've done some testing and you are right byLine is broken, so 
please fill a bug


A bug? I was under the impression that this function was *intended* 
to work only with UTF-8 encoded files.


Impression is nice but there is nothing about it, so anyone who will 
read doc will expect it to work on any encoding.
And from doc I see there is a way how one can select encoding and even 
select Terminator and its type, and this does not works so I expect it 
is a bug.


Another wierd behaviour is when you read file as wstring it will try to 
decode it as utf8, then encode it to utf16, but even if it works (for 
utf8 files), and you end up with wstring lines (wstring[]) and you try 
to save it, it will automaticly save it as utf8. WTF this is really 
wrong and if it is intended it should be documentet better. Right now 
it is really hard to work with dlang stdio.


But I hoppe it will be deprecated someday and replace with something 
what support ranges and async io

Re: Parsing a UTF-16LE file line by line, BUG?

[pineapple via Digitalmars-d-learn]

On Wednesday, 4 January 2017 at 19:20:31 UTC, Nestor wrote:
On Wednesday, 4 January 2017 at 18:48:59 UTC, Daniel Kozák 
wrote:
Ok, I've done some testing and you are right byLine is broken, 
so please fill a bug


A bug? I was under the impression that this function was 
*intended* to work only with UTF-8 encoded files.


I'm not sure if this works quite as intended, but I was at least 
able to produce a UTF-16 decode error rather than a UTF-8 decode 
error by setting the file orientation before reading it.


import std.stdio;
import core.stdc.wchar_ : fwide;
void main(){
auto file = File("UTF-16LE encoded file.txt");
fwide(file.getFP(), 1);
foreach(line; file.byLine){
writeln(file.readln);
}
}

Re: Parsing a UTF-16LE file line by line, BUG?

[Nestor via Digitalmars-d-learn]

On Wednesday, 4 January 2017 at 18:48:59 UTC, Daniel Kozák wrote:
Ok, I've done some testing and you are right byLine is broken, 
so please fill a bug


A bug? I was under the impression that this function was 
*intended* to work only with UTF-8 encoded files.

Re: Does anyone know of an sdl-mode for Emacs?

[Russel Winder via Digitalmars-d-learn]

On Wed, 2017-01-04 at 17:24 +, Atila Neves via Digitalmars-d-learn
wrote:
> It's getting tedious editing dub.sdl files with no editor 
> support. If nobody's written one, I will.
> 

Emacs has an sdlang-mode. It's on MELPA so installable via packages.

-- 
Russel.
=
Dr Russel Winder  t: +44 20 7585 2200   voip: sip:russel.win...@ekiga.net
41 Buckmaster Roadm: +44 7770 465 077   xmpp: rus...@winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder

signature.asc
Description: This is a digitally signed message part

Re: Parsing a UTF-16LE file line by line?

[Daniel Kozák via Digitalmars-d-learn]

Daniel Kozák  napsal St, led 4, 2017 v 6∶33 :


Nestor via Digitalmars-d-learn  
napsal St, led 4, 2017 v 12∶03 :

Hi,

I was just trying to parse a UTF-16LE file using byLine, but 
apparently this function doesn't work with anything other than 
UTF-8, because I get this error:


"Invalid UTF-8 sequence (at index 1)"

How can I achieve what I want, without loading the entire file into 
memory?


Thanks in advance.
can you show your code, byLine should works ok, and post some example 
of utf16-le file which does not works


Ok, I've done some testing and you are right byLine is broken, so 
please fill a bug

Re: Parsing a UTF-16LE file line by line?

[Daniel Kozák via Digitalmars-d-learn]

Nestor via Digitalmars-d-learn  
napsal St, led 4, 2017 v 12∶03 :

Hi,

I was just trying to parse a UTF-16LE file using byLine, but 
apparently this function doesn't work with anything other than UTF-8, 
because I get this error:


"Invalid UTF-8 sequence (at index 1)"

How can I achieve what I want, without loading the entire file into 
memory?


Thanks in advance.
can you show your code, byLine should works ok, and post some example 
of utf16-le file which does not works

Does anyone know of an sdl-mode for Emacs?

[Atila Neves via Digitalmars-d-learn]

It's getting tedious editing dub.sdl files with no editor 
support. If nobody's written one, I will.


Atila

Parsing a UTF-16LE file line by line?

[Nestor via Digitalmars-d-learn]

Hi,

I was just trying to parse a UTF-16LE file using byLine, but 
apparently this function doesn't work with anything other than 
UTF-8, because I get this error:


"Invalid UTF-8 sequence (at index 1)"

How can I achieve what I want, without loading the entire file 
into memory?


Thanks in advance.

Re: String characters not extended

[Anonymouse via Digitalmars-d-learn]

On Tuesday, 3 January 2017 at 19:40:20 UTC, Daniel Kozák wrote:
Why do not use CP_UTF8 constant instead of 65001? It is safer, 
easier to read and understand


I have no reason to back it up with. I'm literally just 
copy/pasting what others have suggested I use.