[Home] [Downloads] [Search] [Help/forum]


Register forum user name Search FAQ

Gammon Forum

[Folder]  Entire forum
-> [Folder]  MUSHclient
. -> [Folder]  Lua
. . -> [Subject]  Memoized Factorial function

Memoized Factorial function

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page


Pages: 1  2 

Posted by Twisol   USA  (2,257 posts)  [Biography] bio
Date Reply #15 on Fri 03 Sep 2010 11:29 PM (UTC)
Message
*shrug* It really just counts up instead of down, which is necessary to permit memoization down the line. A non-memoizing tail-recursive function is dead easy: my final code snippet in my first post here does this, except it does memoize the final result.

I'd personally prefer the tail-recursive one, because I know I can pass just about any number and not risk a stack overflow. (Whether Lua can represent the result accurately is a different matter.) Since the speed difference is minute, it's a very self-contained black box, and it's not at risk of overflows, it's the one I'd prefer.

Then again, I'd probably use the iterative one over any of the others.

'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #16 on Sat 04 Sep 2010 12:02 AM (UTC)
Message
You guys are only scratching the surface here. See:

http://en.wikipedia.org/wiki/Factorial



:P

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #17 on Sat 04 Sep 2010 12:09 AM (UTC)
Message
I knew about the optimizations for very large factorials by finding the prime factors, however I don't think the computation here would go that far for it to be useful.

In fact, I think that the memoization described here is not optimal; you are much more likely to be calling the same factorial many times than a whole bunch of them. So it's ok to memoize the "standard" way, namely, "have I seen this question before, if yes, return the answer, if not, compute it from scratch" -- that would considerably improve performance in the case of repeated identical questions, but obviously would perform worse if the common pattern is to do things like I did in my test case.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by WillFa   USA  (525 posts)  [Biography] bio
Date Reply #18 on Sat 04 Sep 2010 12:59 AM (UTC)
Message
Good morning , Nick.

And again, I'm agreeing with David regarding standard memoization versus building a lookup table.

I've started building the combination and hypergeometric distribution functions, and I'm seeing trends on common values. To list a few major ones: 60 card deck. 1,2,3, or 4 instances of most cards. 17-25 lands... It's easier to just memoize those values.



As an aside, since David and Nick appear to know more about this Math type stuff... ;)

I'm stumped about combining the probabilities though. i.e. I want to track the probability that I'll have an opening hand of 2 lands and a "1 drop" and a "2 drop" (1 mana and 2 mana casting cost) creatures in my first 9 cards (two turns).

I have the algorithm for finding the probability of having 2 lands in the first 2 turns. h(21,60,9,2) which is (c(21, 2) * c(60-21, 9-2))/ c(60,9) . c computes combinations.
Likewise either of the critters can be found. h(9,60,9,1)

But how would I combine those 3 probabilities to find the intersection of them?
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #19 on Sat 04 Sep 2010 04:46 AM (UTC)
Message
I am no great expert in probability, but I think you multiply them. For example, if there probability of being male is 0.5 and the probability of having red hair is 0.3 the the probability of a random person being a male red-head is 0.5 * 0.3, namely 0.15.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #20 on Sat 04 Sep 2010 06:49 AM (UTC)

Amended on Sat 04 Sep 2010 06:52 AM (UTC) by David Haley

Message
Unfortunately it is not so easy. Multiplication only works when the events are independent. If you assume that the events "child is male" and "child is red-haired" have any correlation, then a straight multiplication will misstate the probabilities.

There are a few ways to approach this; one is called the inclusion/exclusion principle:
http://en.wikipedia.org/wiki/Inclusion-exclusion_principle

and in particular:
http://en.wikipedia.org/wiki/Inclusion-exclusion_principle#In_probability

Another is to compute conditional probabilities; they are defined as:

P(A|B) = P(A and B) / P(B)

Or in other words, the probability of event A occurring given that B has occurred is equal to the probability that A and B occur at the same time divided by the probability that B occurs on its own.

You can rearrange this to say that the probability of A and B is equal to P(A|B) * P(B). Then you need only compute P(A|B), which in and of itself might be non-obvious.



By the way, let's see how this applies in the red-haired male child example, assuming independence of masculinity and red-hair.

P(Red and Male) = P(Red given Male) / P(Male)
= 0.3 / 0.5
= 0.15

which is exactly the result of multiplying the probabilities. Note that because we assumed independence, we were able to write that P(Red given Male) = P(Red). Had we not assumed independence, we would not have been able to write that.

Of course in the card-drawing case independence won't apply. Clearly, if you drew 7 lands, you wouldn't be able to draw 5 other cards in your first hand. So the fact that one of them held true will affect the other.

I'd have to sit down and think about this for a while longer and get all the parameters before I could give an actual answer to this, and besides combinatorics were never my strong suit, but it'd be fun to give it a shot. You might even be able to derive an answer empirically if you are willing to make enough simplifying assumptions. (The more simplifications you make, the fewer combinations there are to look at.)

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #21 on Sat 04 Sep 2010 07:16 AM (UTC)
Message
WillFa said:

For now, let's just assume that every card is unique and there's no duplicates in there. ... Of course, most decks have multiple basic lands and up to 4 of the same card ...


If you don't mind my pointing it out, these two statements completely contradict each other.

I'm not totally sure how probability is going to help you here. If there are quite a few lands in the pack, then drawing one doesn't really lower the probability of getting another (by much). However if there is a unique card, then yes, drawing it lowers the probability of another to zero.

Besides the rules can change. To quote from them: "Whenever a card's text directly contradicts the rules, the card takes precedence."

So woe betide the player who draws a card that states that the laws of probability have become invalid.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by WillFa   USA  (525 posts)  [Biography] bio
Date Reply #22 on Sat 04 Sep 2010 02:12 PM (UTC)
Message
would

Quote:
For illustration, let's just assume that every card is unique and there's no duplicates in there. ... In reality, most decks have multiple basic lands and up to 4 of the same card ...


Have been better?
[Go to top] top

Posted by David Haley   USA  (3,881 posts)  [Biography] bio
Date Reply #23 on Sat 04 Sep 2010 05:36 PM (UTC)
Message
But even then, you're looking for the probability of drawing two lands -- so even if the lands are different, there is at least some notion of categorization going on. So I think you can't assume total uniqueness.

Quote:
So woe betide the player who draws a card that states that the laws of probability have become invalid.

Made me smile. :-)

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top

Posted by Nick Gammon   Australia  (22,973 posts)  [Biography] bio   Forum Administrator
Date Reply #24 on Sat 04 Sep 2010 08:49 PM (UTC)
Message
WillFa said:

would [ .. a rewording of the problem ..] Have been better?


I'm just trying to gently suggest that if you look up probability ideas for (say) a deck of 52 playing cards (which are indeed unique) and try to extrapolate to the Magic cards, where you acknowledge duplicates, the results may not hold.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top

Posted by WillFa   USA  (525 posts)  [Biography] bio
Date Reply #25 on Sat 04 Sep 2010 11:34 PM (UTC)

Amended on Sat 04 Sep 2010 11:37 PM (UTC) by WillFa

Message
But looking up probabilities for decks of cards leads to urn problems which give examples of multivariate hypergeometric distributions... which is what I needed. :)

(I had the hypergeometric functions... just needed to find the multivariate ones to make headway. :) )
[Go to top] top

Posted by WillFa   USA  (525 posts)  [Biography] bio
Date Reply #26 on Mon 06 Sep 2010 08:14 AM (UTC)

Amended on Mon 06 Sep 2010 04:32 PM (UTC) by WillFa

Message
If anyone's curious... (which I don't think anyone is...)



do
  local memofac = {[0] = 1}

  local function memo_fac(x)
    while #memofac < x do
      local newkey = #memofac+1
      memofac[newkey] = memofac[#memofac] * (newkey)
    end
    return memofac[x]
  end

  function factorial(x)
    assert(type(x) == 'number' and x>=0, "X must be a non-negative integer.", 2)
    return memofac[x] or memo_fac(x)
  end
end


function comb (n,k)
    assert (type(n) == "number" and type(k) == "number" and n >= k, 
      "Expected numbers for Population and Samples. Samples must be smaller than Population")
    return factorial(n)/(factorial(n-k)*factorial(k))
end

function draw (deckSize, handsize, ...)
    local numInDeck = 1
    local numDrawn = 2
    local desired = {...}
    local padding = {deckSize, 0}
    local padDraws = 0
    local prob = 0

    for _, v in ipairs(desired) do
        padding[numInDeck] = padding[numInDeck] - v[numInDeck]      --number of cards not in the requested sets
        padding[numDrawn] = padding[numDrawn] + v[numDrawn]         --total number of cards requested
    end

    for _,i in ipairs(desired) do
        local workingProb = 0
        for j = 0, math.min( i[numInDeck]-i[numDrawn], handsize - padding[numDrawn] ) do
            workingProb = comb(padding[numInDeck] , handsize - padding[numDrawn] - j)
            for _,k in ipairs(desired) do
                if k == i then
                    workingProb = workingProb * comb(k[numInDeck], k[numDrawn] + j)
                else
                    workingProb = workingProb * comb(k[numInDeck], k[numDrawn])
                end
            end
            workingProb = workingProb / comb(deckSize, handsize)
            prob = prob + workingProb
        end
    end

    return prob
end



This gives a "draw" function that will take in the size of the deck, how many cards you're drawing, and then any number of tables with the number of cards in the deck and how many you want...


print(draw(60, 7, {17,2}, {8,2}, {4,1}, {8,1}))

0.038349597671632



The formula btw is:

 comb(17,2) * comb(8,2) * comb(4,1) * comb(8,1) * comb(60 -17-8-4-8 , 5 -2-2-1-1) / comb(60, 5)

That figures out the probability of getting EXACTLY 2 of a, 2 of b, 1 of c, and 1 of d, and 1 not in the previous sets. The loop sums the probabilities so you're getting AT LEAST 2,2,1,1 of the requested cards... (i.e. 3,2,1,1,0 ; 2,3,1,1,0 ; 2,2,2,1,0; 2,2,1,2,0...)

[Go to top] top

Posted by Twisol   USA  (2,257 posts)  [Biography] bio
Date Reply #27 on Mon 06 Sep 2010 08:31 AM (UTC)

Amended on Mon 06 Sep 2010 08:32 AM (UTC) by Twisol

Message
Very nice! :)

Incidentally...
local factorial = setmetatable({[0] = 1}, {
  __index = function(t, x)
    assert(type(x) == 'number' and x>=0, "X must be a non-negative integer.", 2)
    while #t < x do
      local newkey = #t+1
      t[newkey] = rawget(t, #t) * newkey
    end
    return rawget(t, x)
  end,
  
  __call = function(t, x)
    return t[x]
  end,
})

Note(factorial(50))

This form greatly appeals to me. ^_^

'Soludra' on Achaea

Blog: http://jonathan.com/
GitHub: http://github.com/Twisol
[Go to top] top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


69,150 views.

This is page 2, subject is 2 pages long:  [Previous page]  1  2 

It is now over 60 days since the last post. This thread is closed.     [Refresh] Refresh page

Go to topic:           Search the forum


[Go to top] top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

[Home]


Written by Nick Gammon - 5K   profile for Nick Gammon on Stack Exchange, a network of free, community-driven Q&A sites   Marriage equality

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( https://gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Hosted at HostDash]