• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Junilu Lacar
  • Liutauras Vilda
Sheriffs:
  • Paul Clapham
  • Jeanne Boyarsky
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
Bartenders:
  • Jesse Duncan
  • Frits Walraven
  • Mikalai Zaikin

Algorithm explanation

 
Saloon Keeper
Posts: 13999
315
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Marshal
Posts: 75842
361
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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®:-
 
Bartender
Posts: 1249
87
Hibernate jQuery Spring MySQL Database Tomcat Server Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.

  • StackCallsNCalculations.png
    [Thumbnail for StackCallsNCalculations.png]
     
    Campbell Ritchie
    Marshal
    Posts: 75842
    361
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    Bartender
    Posts: 1249
    87
    Hibernate jQuery Spring MySQL Database Tomcat Server Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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 .. ..

    Another small example:
    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
    Marshal
    Posts: 75842
    361
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    Bartender
    Posts: 1249
    87
    Hibernate jQuery Spring MySQL Database Tomcat Server Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Marshal
    Posts: 75842
    361
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Bartender
    Posts: 1249
    87
    Hibernate jQuery Spring MySQL Database Tomcat Server Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Me too, yes probably...
     
    Ranch Hand
    Posts: 231
    1
    Eclipse IDE Opera Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    Saloon Keeper
    Posts: 13999
    315
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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.
     
    Don't get me started about those stupid light bulbs.
    reply
      Bookmark Topic Watch Topic
    • New Topic