Factorial Question

[dedndave]

it might be simplest to write a routine to calculate the number of permutations for a given (n,r)

then, use the result of that routine to help calculate the number of combinations by dividing by r!

the low-level routine should be able to calculate (n-r)!
then, just use a value of 1 for r and use the same routine to calculate n! and r!
well - that is one approach   :bg
if you factor the n!/(n-r)! first, it would be faster according to the doc
the code for the low-level routine would be the same

Code Select Expand

combinations(9,5):

    2 x 3 x 4 x 5 x 6 x 7 x 8 x 9        6 x 7 x 8 x 9
  ---------------------------------  =  ---------------
  ( 2 x 3 x 4 x 5 ) x ( 2 x 3 x 4 )        2 x 3 x 4
if you want it to be even faster, you could factor out the primes from the resulting equation before evaluating it

Code Select Expand

combinations(9,5) = 2 x 3 x 3 x 7

[FORTRANS]

Hi,

can someone double check the big ones?

Code Select Expand


000000000EBA8F91E823EE3E18972ACC521C1C87CED2093CFDBE800000000000:000000000000
00000002FDE529A3274C649CFEB4B180ADB5CB9602A9E0638AB2000000000000:000000000000
0000009E90719EC722D0D480BB68BFA3F6A3260E8D2B749BB6DA000000000000:000000000000
0000217277F77E01580CD32788186C96066A0711C72A98D891FC000000000000:000000000000
00072F97C62C1249EAC15D7E3D3F543B60C784D1CA26D6875D24000000000000:000000000000
0192693359A4002B5A4C739D65DA6CFD2BA50DE4387EED9C5FE0000000000000:000000000000
59996C6EF58409A71B05BE0BADA2445EB7C017D09442E7D158E0000000000000:000000000000


   And I get a hexadecimal display for my fixed point routines.

Cheers,

Steve N.

[clive]

Thanks, looks good.
-Clive

[dedndave]

after looking at what it might take to write some good "all-purpose" combinatorial routines,
i have come to the conclusion that the range used by the intended application is quite important
i.e. i don't think it is practical to write a set of routines to cover all uses
that is because the prime number "search" and squarerooter used for factoring can be optimized differently for different ranges
it does look like ling long kai fang could help in factoring terms, though   :bg

[z941998]

I to have seen different approaches.

dedndave, I knew about the shortcuts persay with nCr process, but the link was interesting, especially since I graduated from John F. Kennedy here in Bloomington, MN, kinda hit home.

Anyhow, my problem was that I was staying within the register boundary.  After reviewing your routines for large numbers I change my thought process.  So far, I wrote five different tests, three worked ok and the other two are still in-process.  At this point I am convinced that there should be a logical decision point to use Ling Long Kai Fang, just haven't determine where to establish this barrier point.

I did note the formula Length = (Trunc(Log(2) * Bits) + 1 and using algebra I found that Bits = (Length - 1) / Log(2).
This may be part of the answer to the above.  I have been trying some data driven usage of memory to produce the desired results.
Example 150! I allocate memory according to the formulas.  The problem is that I have to de-reference during calculation (ie overhead) and it slows down the entire process, which means I won't get to Raymonds mark, and it screws up the carry propagation process also.  But a standalone rounting without allocation I am close.  Calculating the numbers is not the problem, converting to decimal base and displaying tends to be another slow down point.  I even went to LLFK to help with this.

I think we should establish a rule that n values should stay in the range of WORD, ie 16 bits. This will get us a functional method and then we can go for gold like Factor(15 Googlebytes).

I have also collected some reference material but want to clean it up before posting here.

[z941998]

See Attachment Post1

Post2 will be in the next post

[z941998]

Post2

[dedndave]

Steve,
150! is a huge number
however, you wouldn't have to handle nearly that large of a value if you write the routine to
calculate the quantity of combinations or permutations instead of calculating the individual factorial(s)

if you are doing something like calculating odds for a lottery, you probably want combinations
all lotteries that i know of use combinations
i.e. the set (1,2,3,4,5,6) is the same lottery ticket as the set (2,1,3,4,5,6)
you don't have to guess which order the numbers are picked
if you did, you wouldn't have a snow-ball's chance in hell of getting a winner   :P
the odds of winning are bad enough as it is - lol
this complicates the equation slightly, but reduces the size of the end result considerably

i have heard of one lottery where you picked 4 digits in the order chosen
but, that was in the movie "Die Hard 2" - lol

[dedndave]

i meant to ask, Steve
other than "dword register size", could you tell me more about the range you intend to use this ?
like C(160,10) or something ?

[z941998]

I have all combinations of all lotteries covered.  I can win pick-5's with 31 numbers at least once a week, but for only $12,500, not really a good payoff rate.  Going after the big guys its about once a year and a half, at $200,000, a better payoff rate, but like you say hitting the grand daddy won't happen in my lifetime.  Like grasshopper, I am chipping away at the mountain.

But I also have another application that requires me to go beyond this effort.  I am creating and encription scheme that is intertwined with 150 different faciities for my corporation and don't want any violations and this includes server to server connectivity and simultaneously backdoor verification (thereby the permutations) at each step of an authorized data access.  This also applies to electronic servaillence,

After looking at the large number multipling process I was thinking that the multipliier be held with a 16-bit boundary (64k), even thou the multiplicand and reach unlimited values.  Even with Raymonds benchmark such as C(15000,900) is still in range.

The multiplicity stuff you provided works good.  Just have to go to exponotational levels and then back, but at least at more managable level.

[dedndave]

so, if you had a routine that could handle C(15000,rrrr), you'd be covered ?

[z941998]

The C(15000,rrrr) covers Raymonds benchmark for 9ms.

I needed a C(150, 23) and C(150, 19) setup, which I have completed.

But I am still trying to see if I can do the benchmark.  I can do C(1000,200) but its at about 1 sec, no where near 9ms.

[dedndave]

how long does your C(150,nnn) take ?
i don't think Ray pre-factored to get that time
C(15000,5000) - that sounds like a euler puzzle   :P

but, what i was looking for was "what are some practical requirements"
i don't know of any lottery that has you pick 5000 numbers from 1 to 15000 - lol
can you imagine filling out the pick ticket ?
let me see - there is my birthday, Zara's birthday, Jade's birthday.....
.....then, there is Leon, my forth cousin twice removed - i forget his birthday

[z941998]

When I get home I will post what I have done.

Picking 5000 numbers sounds more like Keno, which has higher odds than Lotto's I work with.  Albeit when I go to Vegas, I play Kings with Keno.

I personally cut off permutations/combinations for Lottos at 64C5 or 64C6 as this covers 98% of the lotteries.

But when looking at security, company projections, or whatever, outside of the gambling environment that I am involved with, I had to raise the bar.  Example. when doing a Monty Carlo simulation for projecting income and expenses with 150 different facilities that produce various results you can get a very tight correlation (bell curve) with a high kurtosis and low variance.  And when you have 23 sources of revenue, some bankers and investors want to see the probabilities of various senarios with PEST, PERT, SWOT analysis that support a lower risk than what they precieve.  Example Bankers only lend at a rate of about 8% for Bowling Centers whereas private investors will lend at a 90% rate.

Sorry about getting off base, I get excited when things start coming together, some of which credit belongs to you.

[z941998]

Here's one of the test's I did.  Compile as console with math.asm as the main program.

I have not completed the divide portion yet, but the factorials up to the final divide point are done.  I just have to convert to large divide format, no time as it has been crazy here the last few days.

I also have been doing some other tests, so compare source code to display results, example Multiplicity.