Algorithm explanation

[Stephan van Hulst]

Campbell Ritchie wrote:He did say that factorials were only defined for positive numbers.

I'm strongly of the opinion that undefined behavior should be caught as soon as possible. In this case I would throw an IndexOutOfBoundsException for negative arguments.

[Campbell Ritchie]

The C code I showed has the unsigned keyword in, so no negative arguments can get past it. Keep quiet about −64. I would write something like this in Java®:-

public static long factorial(int i)
{
   if (i < 0)
   {
      throw new IllegalArgumentException("Negative values not permissible.");
   }
   if (i > 21) // largest factorial fitting into a long: not necessary for BigInteger
   {
      throw new ArithmeticException("Overflow error for argument i = " + i);
   }
   return calculateFibonacci(i);
}

private static long calculateFibonacci(int i)
{
   return i == 0 ? 1L : calcuateFibonacci(i - 1) * i;
}

[Ganesh Patekar]

Campbell Ritchie wrote:He did say that factorials were only defined for positive numbers.

Yes he did, I thought from programmers perspective. Indeed, the topic of video was just about recursion so validations shouldn't be expected.

Oh! yes only one conditional operator rather than 2 returns would have been much better.

Saying factorials were only defined for positive integers rather than natural numbers which include 0

I googled about It, I found some say natural numbers begin with 0 whereas others say begin with 1. Here Wiki: Natural number

I shall let you explain the output for 64! and 66! and −64!

I did some program over Here online, max size of (64 bit )unsigned long int is 18446744073709551615.

When result of multiplication of unsigned numbers goes beyond the max range i.e. 18446744073709551615 they can't overflow but instead wrap around using the properties of modulo like below

When ___* 62 calculates. ( This is previous multiplication's value 3098476543630901248, 2^N where N is the number of bits in the value representation of the type)

( ( 3098476543630901248 * 62 ) % pow( 2, 64 ) ) = 7638104968020361216 then this value returned here ___ * 63 and multiplies with 63 same like 62.

When ___* 63 calculates.

( ( 7638104968020361216 * 63) % pow( 2, 64 ) ) = 1585267068834414592 then this value returned here ___ * 64 and multiplies with 64.

When ___* 64 calculates.

( ( 1585267068834414592 * 64) % pow( 2, 64 ) ) = 9223372036854775808

This is how we got 64! = 9223372036854775808 and similarly we get 21! = 14197454024290336768

We get 65! = 9223372036854775808 then this value returned here ___ * 66 and multiplies with 66.

When ___* 66 calculates, we get.

( ( 9223372036854775808 * 66) % pow( 2, 64 ) ) = 0
That is why 66! = 0

When ___* -64 happens

It will keep calling factorial(unsigned long int i) like factorial( -64 - 1 ) * -64 then factorial( -65 - 1 ) * -65 then factorial( -66 - 1 ) * -65 then.... at last gives Segmentation fault.

Figure of how calls in stack made when i = 64.

[Campbell Ritchie]

Ganesh Patekar wrote:. . .  some say natural numbers begin with 0 whereas others say begin with 1. . . .

You need to be very careful about such websites. You need to choose the one that matches your present requirements, so those that say 0 is a natural number are correct. But when you want 0 not to be a natural number, you look at the other websites

I shall let you explain the output for 64! and 66! and −64!

. . . When result of multiplication of unsigned numbers goes beyond the max range i.e. 18446744073709551615 they can't overflow  . . .

Where did you find that about not overflowing? Surely what you describe is overflow? Remember that every time you multiply by an even number you add at least one 0 bit to the right end of the number and when you get to × 66, you have added 64 0 bits, so you get 0. 21! is the last factorial which will fit into 64 bits; all values above 21! suffer overflow errors.

When ___* -64 happens

It will keep calling factorial(unsigned long int i) like factorial( -64 - 1 ) * -64 then factorial( -65 - 1 ) * -65 then factorial( -66 - 1 ) * -65 then.... at last gives Segmentation fault. . . .

But unsigned doesn't permit negative numbers

[Ganesh Patekar]

Campbell Ritchie wrote:But when you want 0 not to be a natural number, you look at the other websites

That's what I did

Where did you find that about not overflowing? Surely what you describe is overflow?

Here Yes It overflows, so many sites says that but why remember this one only dunno, I think I had sleepy eyes
Oh I see, yes all values above 21! suffer overflow.  Thank you for clearing my doubt.

But unsigned doesn't permit negative numbers

Ya I read your previous comment but just thought to try doing It practically. I've run your same program Here just added print statement in it, It keeps printing something like 18446744073709430101 .. ..

/* factorial program factorial.c */
#include <stdio.h>
#include <stdlib.h>
 
unsigned long int factorial(unsigned long int);
 
int main(int argc, char **argv)
{
    int i = -64;
    printf("%d! = %lu\n", i, factorial(i));
    return 0;
}
 
unsigned long int factorial(unsigned long int i)
{
    printf("%lu\n:",i);// new added line
    return i == 0 ? 1 : factorial(i - 1) * i;
}

Another small example:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
    unsigned long int no = -4;
    printf("-4 = %lu\n", no);
    no = -10;
    printf("-10 = %lu\n", no);
    return 0;
}

Output:
‐4 = 18446744073709551612
‐10 = 18446744073709551606

I also came across about this may be on that same site, when we assign negative value to unsigned long int It calculates It's value like below. This program produced same output. No notion, It's correct Or not.

For -4:
( 2^64 ) - 4  =  18446744073709551612

For - 10:
( 2^64 ) - 10  =  18446744073709551606

[Campbell Ritchie]

Ganesh Patekar wrote:. . . Here Yes It overflows, so many sites says that but why remember this one only dunno, I think I had sleepy eyes . . .
‐4 = 18446744073709551612
‐10 = 18446744073709551606 . . .

There are all sorts of odd things in that SO link; I still cannot see that calculating the number modulo 2⁶⁴ is any different from overflow. I am also surprised that he suggests that signed integer overflow is unpredictable; I always thought overflow is always predictable. Of course there are lots of things which are undefined in C and strictly defined in Java®.
Yes, since C is not a strongly‑typed language, the −64 is converted to 2⁶⁴ − 64 and you simply run out of stack space. If you managed to do that in Java®, you would suffer a stack overflow error.
You have put no end of effort into sorting out this problem

[Ganesh Patekar]

Since I found this. I suppose, I need to rethink and rectify my previous statements.

Regarding unsigned long int can't overflow:

Source

The CERT® C Coding Standard, Second Edition by Robert C. Seacord, Ch 4. Page No 112 wrote:The C Standard, 6.2.5 paragraph 9, States: "A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type. This behavior is more informally called unsigned integer wrapping.

 

Regarding signed integer overflow is unpredictable:

Undefined behavior

Undefined behavior, Wiki wrote:In computer programming, undefined behavior (UB) is the result of executing computer code that does not have a prescribed behavior by the language specification the code adheres to, for the current state of the program (e.g. memory). This happens when the translator of the source code makes certain assumptions, but these assumptions are not satisfied during execution.
The behavior of some programming languages - most famously C and C++ - is undefined in some cases.

Undefined behavior is often unpredictable and a frequent cause of software bugs. In the C community, undefined behavior may be humorously referred to as "nasal demons", after a comp.std.c post that explained undefined behavior as allowing the compiler to do anything it chooses, even "to make demons fly out of your nose"

Beneath Benefits from undefined behavior It says:
The value of x cannot be negative and, given that signed integer overflow is undefined behavior in C.
.....  ....
.....  ....
After second example:
Another benefit from allowing signed integer overflow to be undefined is that it makes it possible to store and manipulate a variable's value in a processor register that is larger than the size of the variable in the source code.

Campbell Ritchie wrote:You have put no end of effort into sorting out this problem

I remember, the first language I learned was Pascal in 2007 then C, VB, C++, DS, SQL, Java etc etc. We used to learn programs by dry run on papers and C's pointers and string programs were quite interesting. After long long time I did a C program. Thank you for being the reason behind It

[Campbell Ritchie]

Now that is interesting, and I had never seen that before. I suspect integer wrapping will produce exactly the same result as overflow however.

[Ganesh Patekar]

Me too, yes probably...

[Rajdeep Biswas]

Stephan van Hulst wrote:Understanding recursion lies in believing that the recursive step "just works".

When I tried to solve it, thinking about individual movements confused me. Then I trusted recursion, thought about a single disk case calling that in recursion, and wrote the base condition, again just a print. It worked. When I go into it, it still utterly confuses me. So I am half in half out!    

[Stephan van Hulst]

Here's a nice example I read in an online article somewhere:

Say there's a long queue of people, and you want to know how many are in the queue. You can simply ask the guy in front of you how many people there are in the queue, and then add 1 for yourself. You don't care how the guy in front of you got the answer, you just trust that it's correct.

The guy in front uses the same technique. This goes on all the way until the guy at the front of the queue is asked how many people there are in the queue. The guy at the front sees no people in front of him, so he just reports 1. He is the base case.

final class PersonInQueue {

  private final PersonInQueue next;

  int askForLengthOfQueue() {
    if (next == null)
      return 1;

    return next.askForLengthOfQueue() +1;
  }
}