Google Analytics

Friday, 18 February 2022

Factorials (or Bonding with Brague)

Dear Bob,

As I am sure you know, the factorial of any positive whole number is that number multiplied by all the numbers between it and 1.

So the factorial of 3 = 1 x 2 x 3 = 6
And the factorial of 5 = 1 x 2 x 3 x 4 x 5 = 120

I am also sure that, as a computer programmer, you could quickly write a program to calculate the factorial of any number N. One way to do it would be to set up a counter to cycle through all the numbers between 1 and N, multiplying each by a running total that is initially set to 1. In an imaginary programming language it might look like this:

RunningTotal = 1
FOR Counter = 1 to N
Multiply RunningTotal by Counter; (thereby altering the value of RunningTotal)
The factorial of N = RunningTotal

So, in calculating the factorial of 5, each step of the cycle would produce the following values:

 Counter   Multiplication of
 RunningTotal x Counter 
 New Value of
 RunningTotal 
1 1  x  1 1
2 1  x  2 2
3 2  x  3 6
4 6  x  4 24
5 24  x  5 120

But there is a more elegant way. This involves thinking of the factorial of any number N as being that number multiplied by the factorial of N-1.

So the factorial of 3 = 3 x 2 = 6
And the factorial of 5 = 5 x 24 = 120
And the factorial of 6 = 6 x 120 = 720

In our imaginary programming language, the program to calculate factorials using this method might look like this:

The factorial of 1 = 1
The factorial of N = N x the factorial of (N-1)

This is known as a recursive function because it has to re-use itself at each step of the calculation. For example:

The factorial of 5 = 5 x (the factorial of 4)
    The factorial of 4 = 4 x (the factorial of 3)
        The factorial of 3 = 3 x (the factorial of 2)
            The factorial of 2 = 2 x (the factorial of 1)
                The factorial of 1 = 1 (this causes the calculation to “unwind”)
            So, the factorial of 2 = 2 x 1 = 2
        So, the factorial of 3 = 3 x 2 = 6
    So, the factorial of = 4 x 6 = 24
So, the factorial of 5 = 5 x 24 = 120

Isn’t that just exquisite!

Now, for homework, please would you explain the operation of recursive descent parsing giving examples from the Hebrew and Cherokee languages.

Sincerely yours

44 comments:

  1. omg, this gave me the colly wobbles, I hated Maths at school and still hate it. lol
    Briony
    x

    ReplyDelete
    Replies
    1. I am the proud owner of a grade F A-level maths certificate.

      Delete
  2. As a Wee Lassie I went out with decades ago used to say:
    Golly !
    She was a dab hand at the factorials.
    Unlike Bob, she didnae have the Hebrew and Cherokee, but she could curse like a soldier in Latin. The only time she used profanities.

    Do you know the books of Ian Stewart, Tasker?
    I have four of them in paperback.
    Calculating the Cosmos (How Mathematics Unveils the Universe).
    Incredible Numbers.
    Hoard of Mathematical Treasures
    Cabinet of Mathematical Curiosities: my favourite, because it has little drawings I can understand of Magic Stars and Squares and Hexagons, Sacred Turtles, Perpetual Calendars, polyhedrons, antigravity cones, nautilus shells, Pythagorean Triples ... and the Bridges of Konigsberg, but no Immanuel Kant.

    A friend's son was talking about taking ayahuasca, because of some twaddle he had heard from that mystagogue Graham Hancock on YouTube.
    I told him to take up piano lessons, learn German, and read Professor Ian Stewart, instead of messing with his beautiful brain.

    ReplyDelete
    Replies
    1. Professor Ian Stuart sounds as if he also has a beautiful brain. I'm afraid the only person of that name I know of is Ian Stuart who wrote The Satan Bug.

      Delete
    2. The Satan Bug wasn't a bad movie.
      Directed by John Sturges.
      Richard Baseheart, Anne Francis, and the heroic Dana Andrews who was in the only movie they made from a JD Salinger story, *Uncle Wiggily in Connecticut*, retitled *My Foolish Heart* (1949).

      I am 100 pages into a book by John Kay and Mervyn King (2020).
      *Radical Uncertainty - Decision Making for an Unknowable Future*.
      It is an exciting book in the wake of the global pandemic and financial meltdown of 2008.

      *Mathiness.
      The belief that mathematical reasoning is more rigorous and precise than verbal reasoning, which is thought to be susceptible to vagueness and ambiguity, is pervasive in economics.*

      Daniel Kahneman welcomes the day when algorithms will take over from human decision-making.
      Artificial intelligence will eliminate human errors.

      Delete
  3. Did you set out to make my brain hurt? If so - well done- youhave succeeded!!!

    ReplyDelete
  4. Replies
    1. Then let me tell you a chemistry joke. Why did the attacking army use acid? To neutralize the enemy’s base!

      Delete
  5. ...why I was an English Major.

    ReplyDelete
  6. I got to Line Four of your Blog OK. 60yrs ago this might have been important for O Level but I can't say that it has had to worry me since.

    ReplyDelete
    Replies
    1. Without this kind of thing we'd have no electronic devices, but there's no need to know how an engine works in order to drive a car.

      Delete
  7. You lost me at "Dear Bob," which I am proud to say I did understand. I thought a factorial was a lavatory in a factory or any other industrial premises.

    ReplyDelete
    Replies
    1. I'm beginning to realise how C. P. Snow must have felt.

      Delete
    2. Hey! That's my old joke. Years ago when I was young and cheeky, people would ask "how do you feel?" and I would answer "with my hands"

      Delete
  8. Err, yes. Double checking. Quite right. It is 9am here and off to the shops. I'll be back later to address your Hebrew and Cherokee question.

    ReplyDelete
    Replies
    1. We're all still waiting for you to enlighten us.

      Delete
  9. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. Tasker, I am tempted to say "Elementary, my dear Watson" a la Sherlock Holmes, but that would be unseemly. Actually, i am honored (British, honoured) to have been mentioned in your blog! I thought everybody knew about factorials. Can you do something next with Fibonacci numbers?

      Delete
    2. That is a deceptively clever final sentence.

      Delete
  10. I was okay with the first step, finding the factorial, but completely lost when you introduced N and then the rest of it.

    ReplyDelete
    Replies
    1. It could be done with X if it makes it easier.

      Delete
    2. Absolutely not. I'm fine with numbers on their own, but letters means algebra and that muddles every neuron I own.

      Delete
  11. I don't understand any of this but I feel quite at home with it because both of my sons are computer engineers and before my husband retired he also worked in the field. I'll just say: You and Bob have fun!

    ReplyDelete
    Replies
    1. I've always said that the nature of knowledge is the ability to bore the pants of anyone daft enough to listen.

      Delete
  12. Some of us are cleverer than others, failed maths miserably. ;)

    ReplyDelete
    Replies
    1. I got a grade F in A-level maths. A down to E were the pass grades.

      Delete
  13. This makes my head hurt. (Even though I only skimmed it.) :)

    ReplyDelete
    Replies
    1. As said to Weaver, that may sometimes be a good thing.

      Delete
  14. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. Your imaginary programming language looks a lot like FORTRAN.

      If space is of the essence (and sometimes it is) or time is of the essence (and it always is), why not start with the number for which you want to determine the factorial and work backwards? What I'm trying to say is you could save a step if, instead of 1 x 2 x 3 x 4 x 5 x... all the way to N you want to determine the factorial for, when not start with the N, work backwards: N x (N-1) x (N-2) x ... 5 x 4 x 3 x 2 AND STOP THERE, eliminating the "multiply by 1" iteration because anything multiplied by 1 is, of course, itself. Exit the loop when 1 is encountered. Come to think of it, you could still do ascending instead of descending and just start the loop with 2 instead of 1 because, as all of your readers now know, anything multiplied by 1 is itself. The last (or first) calculation, depending on which way you're going, is unnecessary. Every nanosecond counts.

      The rationale for this time-saving device traces back to my friend Sanford J. Epstein, a self-proclaimed 305-lb. Jew from Burlington, Vermont, and Pompano Beach, Florida, who always wore a Kelly green suit on St. Patrick's Day and changed his name tag to read Sanford J. O'Epstein, who once told me, "If there's a difference that makes no difference, then there is no difference." Sandy, I salute you today. Spoken like a true computer programmer. Tasker, take note. You and I both know what 65,536 means, hands across the sea, and all that. Keep on keeping on.

      Delete
    2. Absolutely, but I decided, as an HCI guy it feels more natural for non-programmers to count up rather than down.
      I learned all about efficiency and compression, Huffman and Hamming and the like, but these days why bother parsing languages recursively when you can just have a massive corpus and let neural networks make sense of it.

      Delete
  15. Dear Tasker, it looks pretty - yet I do not feel any intention even to try.
    I do love complicated legal texts that make the brain swirl - so my brain isn't lazy. It is just that factorials do not allure me, not at all.
    The funny thing was when we had to do many very complicated IQ-tests before getting into our career they found a high markedness in that sector - and I found out that under pressure I can solve those problems easily - sadly they do not interest me - and luckily I don't have to do that any more :-)

    ReplyDelete
    Replies
    1. Sadly, I really do think this kind of thing exquisite. This describes the simplest form of recursion, with one end point. It is possible to have recursion with multiple end points. That truly is witty and pretty.

      Delete
    2. And I am glad that you adore it, Tasker - it is joy for you.
      Sugar and milk in your tea - some like it, others don't.
      We always choose - and hopefully we choose joy&interest - I always like it when people "burn" for something!

      Delete
  16. Hopefully, your next blogpost will be titled "Bondage with Brague". Potentially much more interesting for the rather dumb general readership to which I belong.

    ReplyDelete

I welcome comments and usually respond the same day (unless it looks like you are trying to advertise something).