www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - RosettaCode factorial needs to use longs

reply "Jay Norwood" <jayn prismnet.com> writes:
http://rosettacode.org/wiki/Factorial#D

to whomever is maintaining these:
Need to change all ints to longs in this example to get the 
displayed results since the 15! result requires more than 32 bits.
Mar 08 2014
next sibling parent "Jay Norwood" <jayn prismnet.com> writes:
After changing to longs, I made some test loops, and on release 
build dmd, pc, these are the relative times I measured for the 
different versions of factorial in that example.  So the 
iterative wins, and the functional style results in 4x penalty in 
this case.

duration factorial (hnsecs)=98
duration recFactorial (hnsecs)=151
duration fact (hnsecs)=418
duration tfactorial (hnsecs)=131

each test was like this:

sw.reset();
sw.start();
for (long i=15; i<50; i++){
   rv+=i.tfactorial;
   rv-=i.tfactorial;
}
sw.stop();
writeln("duration tfactorial (hnsecs)=", sw.peek().hnsecs);
Mar 08 2014
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Jay Norwood:


 http://rosettacode.org/wiki/Factorial#D

 to whomever is maintaining these:
 Need to change all ints to longs in this example to get the 
 displayed results since the 15! result requires more than 32 
 bits.


I am maintaining the D entries, I have fixed that factorial code, 
thank you. I don't know why the shown output was for 64 bit 
numbers.

Bye,
bearophile
Mar 08 2014
parent reply Russel Winder <russel winder.org.uk> writes:
On Sat, 2014-03-08 at 21:20 +0000, bearophile wrote:

 Jay Norwood:
=20

 http://rosettacode.org/wiki/Factorial#D

 to whomever is maintaining these:
 Need to change all ints to longs in this example to get the=20
 displayed results since the 15! result requires more than 32=20
 bits.


=20
 I am maintaining the D entries, I have fixed that factorial code,=20
 thank you. I don't know why the shown output was for 64 bit=20
 numbers.


That page appears to quietly ignore the fact that those languages that
use hardware integers cannot correctly compute factorial(25), let alone
factorial(1000), at least assuming 64-bit integer hardware, whereas
those languages using hardware/software numbers as needed (e.g. Python,
etc.) have no problem.

And there doesn't seem to be mention of tail recursion and tail
recursion optimization much either. Pity really, these comparative pages
could be so useful but generally end up as dumping grounds.

Good to see the D examples being more careful about the internal vs
external iteration and recursion vs tail recursion issue.

I wonder though if it would be better to split the examples up rather
than have a single entry. Nothing to do with the code content just to do
with the visual perception. The D code looks big and so bad, whereas
those that split up the examples look small and so good. Can I suggest
partitioning the D entry into four sub entries so as to make it clear
that explicit iteration, implicit iteration, recursion and tail
recursion are all covered?

--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
Mar 09 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Russel Winder:


 That page appears to quietly ignore the fact that those 
 languages that
 use hardware integers cannot correctly compute factorial(25),


The D entry has the same problem. But a pre-condition could be 
added to limit the input.



 I wonder though if it would be better to split the examples up 
 rather
 than have a single entry. Nothing to do with the code content 
 just to do
 with the visual perception. The D code looks big and so bad, 
 whereas
 those that split up the examples look small and so good. Can I 
 suggest
 partitioning the D entry into four sub entries so as to make it 
 clear
 that explicit iteration, implicit iteration, recursion and tail
 recursion are all covered?


OK, I will split the D entry in four parts, but I think an 
average programmer is able to see that code is made of four 
separated functions that do the same thing in different ways and 
it's not a single large chunk of code needed to do the task. 
That's why I didn't bother with four entries.

(In Rosettacode some D entries are designed to be very short and 
sweet, other to be very fast, other to show the kind of elaborate 
code full of static typing and run-time tests you use in a piece 
of code that should be correct, and so on. So the code style 
varies on purpose to show various ways to write D. You can see 
this in the N-Queens problem D entries and elsewhere).

Bye,
bearophile
Mar 09 2014
parent reply Russel Winder <russel winder.org.uk> writes:
On Sun, 2014-03-09 at 10:28 +0000, bearophile wrote:

 Russel Winder:
=20

 That page appears to quietly ignore the fact that those=20
 languages that
 use hardware integers cannot correctly compute factorial(25),


=20
 The D entry has the same problem. But a pre-condition could be=20
 added to limit the input.


I think leaving the code as is, my point was that the whole page has the
problem that most of the implementation aren't actually useful in
practice, even though for any combinatoric problem (cf. bioinformatics,
quant calculations, etc.) this is a rather important function to get
right :-)


=20

 I wonder though if it would be better to split the examples up=20
 rather
 than have a single entry. Nothing to do with the code content=20
 just to do
 with the visual perception. The D code looks big and so bad,=20
 whereas
 those that split up the examples look small and so good. Can I=20
 suggest
 partitioning the D entry into four sub entries so as to make it=20
 clear
 that explicit iteration, implicit iteration, recursion and tail
 recursion are all covered?


=20
 OK, I will split the D entry in four parts, but I think an=20
 average programmer is able to see that code is made of four=20
 separated functions that do the same thing in different ways and=20
 it's not a single large chunk of code needed to do the task.=20
 That's why I didn't bother with four entries.


I don't disagree, any half-way competent programmer should certainly
read it that way. The problem is that when scrolling down the page, the
visual impact is far more important for attention grabbing than the
content itself.


 (In Rosettacode some D entries are designed to be very short and=20
 sweet, other to be very fast, other to show the kind of elaborate=20
 code full of static typing and run-time tests you use in a piece=20
 of code that should be correct, and so on. So the code style=20
 varies on purpose to show various ways to write D. You can see=20
 this in the N-Queens problem D entries and elsewhere).


It might be a good move to collect together all the URLs of codes like
this so that there is a quick way of reviewing and providing feedback.
Minimizing effort to do reviewing makes it more likely to happen.=20

--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
Mar 09 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
Russel Winder:


 It might be a good move to collect together all the URLs of 
 codes like
 this so that there is a quick way of reviewing and providing 
 feedback.
 Minimizing effort to do reviewing makes it more likely to 
 happen.


Code like what? What URLs?

Currently I am maintaining about 850 D source files (plus few 
others in Haskell, Python, C, C++):
http://rosettacode.org/wiki/Category:D

Bye,
bearophile
Mar 09 2014