• ### Custom Factorial Calculations Patch-Assistance Needed For Efficiency

fac.pd
I built a patch that is supposed allow you to enter in a number and calculate the factorial (without using the expressions object).
Factorial of n = n! = n × (n – 1) × (n – 2) × … × 1
Example 5! is 5 × 4 × 3 × 2 × 1 = 120

I used this max msp factorial patch as a guide.

Looking for assistance in making the factorial patch in Pure Data as efficient as possible.
I want to build this patch using Pure Data primitives instead of using the expression object.

Please note that there is a discussion here that using float values instead of integers allows the recursive method for calculating factorials to have higher input values before failure.
https://cycling74.com/forums/recursive-factorial-function-limits

• Posts 10 | Views 795
• @Muology No idea how efficient it is...... but it "works"...... factorial.pd
But there is still a limit...... 198 is it...... in 32-bit extended
If an external exists that will be more efficient.
And [expr] is probably more efficient than my patch, but its limit is 33..... in extended.
Vanilla 0.53 will not show a result for either with input > 34...... a big for extended.and for vanilla.
Most maths functions are built into [expr]........ and fact() is among them........
To see them all open Pd/doc/8.topics/expr.html in your Pd folder....
David.

• @whale-av said:

But there is still a limit...... 198 is it...... in 32-bit extended

How? ...

Vanilla 0.53 will not show a result for either with input > 34...... a big for extended.and for vanilla.

The largest possible exponent in 32-bit float is 38. With an input of 34, you're already reaching this limit. Anything above that will be an incorrect result, so I'd say to extended for providing a false answer and no indication that the result is false. (Unless you meant 64-bit extended... but the exponent limit in 64-bit floats is 308, and 198! = 1.9815524305E370, also outside the limit... so even in 64 bits, 198! is a garbage result.)

hjh

• Just a quick question in this context - would this here be a valid way of comparing performance? I found the difference between the `until`, `sel` and `route` versions quite interesting:

• I don't know the background but GMP has a very efficient algorithm to calculate the factorial, you maybe can take a look on it's sources.

For example it give an immediate exact result of 10000! ( ~= 2,84E35659 )

Work in progress : FCPD a FreeCAD PureData connexion

• Thank you all.
@whale-av
@ben.wes
How would you implement the combinations formula (C (n, r) = n!/r! (n-r)!) in an efficient way? So that an n and r can be entered in and print all possible combinations?
I used the factorial expression object to calculate the combinations formula using- expr (fact(\$f1)) / ((fact(\$f2)) * (fact(\$f1 - \$f2)))
What approach would you take to calculate the combinations formula without using the expressions object?
What approach would you take to calculate the combinations formula with using the expressions object?

Adding a List and or Array
How would you approach being able to add any type of customizable list/array (for example, list/array = A, B, C, D, E, F) and then telling the patch you want to generate any type of combination and then print all possible combinations?
For example, customizable list/array = A, B, C, D, E, F (n)
generate all possible combinations of 2 (r) also customizable
Print-
All possible combinations = 15
A, B
A, C
A, D
A, E
A, F
B, C
B, D
B, E
B, F
C, D
C, E
C, F
D, E
D, F
E, F

Dynamic patching.....
This shows the basics......... 0.all_msg.pd

All objects, messages, arrays GUI's....... and patches...... can be "put"... and connected or disconnected.
Here.... https://puredata.info/docs/developer/PdFileFormat you will find more about the arguments they will accept.

But the easiest way to use dynamic patching is to make your own abstractions...... patches that you will use as "modules".... that you then dynamically place and connect within another patch window.....
Here is a fairly complicated example....... https://forum.pdpatchrepo.info/topic/12808/minx that builds a mixer with a variable number of in and out channels, and then uses connect and disconnect messages to change the input and output patching to the soundcard from controls in the "Channels" and "Busses" windows.
The creation of the patch is controlled in minx_run.pd
David

• @Muology: Just answering to the second part for now ... for generating all combinations of 2 elements, this here will do (subpatch `pd iterate_list` is on the right. should probably be an abstraction ... and the result is not logically ordered).

if you want to create all combinations with arbitrary lengths, it can certainly be done in a similar manner and I'm pretty confident that one could find an abstraction (or external) for this somewhere. I didn't find one yet though and I'd need a little more time and focus to build it, I'm afraid.

list2pairs.pd

• @Muology Just another approach to the second part of your problem ...

You could use binary numbers to find all possible subsets of a list of length n: iterate the numbers from 0 to 2^n - 1 => convert to binary numbers => use digits to select list items ... like this: subsets.pd (The weird backward counting is just to give the resut in a logical order.)

It may not be the most efficient way to do it, because ALL subsets (not just those of a given length) are generated. But it's fully customizable!

• I was quite fascinated by @manuels' patch (thanks for sharing!) and tried to understand what was going on, which led me to rebuilding and documenting the algorithm (possibly needlessly more complicated).

This doesn't add anything to the solution here - but maybe it can be insightful for someone else stumbling upon this thread ...

Posts 10 | Views 795
Internal error.

Oops! Looks like something went wrong!