Rosetta Code

Talk:Fraction reduction: Difference between revisions

Page Discussion

Talk:Fraction reduction (view source)

Revision as of 10:11, 11 September 2019

949 bytes removed ,  4 years ago
m
→‎searching for Optimizations
 
Line 12:
 
::: I was originally toying around with the name:   ''fallacious fraction reductions'',   but I discarded it.   Sounded worse than it was.     -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 11:43, 4 September 2019 (UTC)
 
== searching for Optimizations ==
 
Like PHIX one can create the list/array of all possible Permutations k out of n very effectivly:<BR>
http://rosettacode.org/wiki/Permutations#alternative <BR>
Think of cUsedDigits= 5 digits out of cMaxDigits=9 [1..9]<BR>
The size of the list is cUsedDigits! * binomial_coefficient(cMaxDigits,cUsedDigits)-> 5!*(9!/(5!*(9-5)!) = 15120 <BR>
[12345],[12354] ... [98756],[98765]<BR>
To memorize the used digits one can use a bitset 1..9.Logical AND of two bitsets will show, if at least one digit is part of both numbers.<BR>
Every section with first digit = 1 or 2... has the size of 15120 DIV cUsedDigits = 1680.<BR>
Searching 2* Index (1) = 12345 can start at Index 1680 = 21345<BR>
So one can search n DIV 2 .. n div 9 and multiples of those numbers.<Br><Br>
 
I think one good optimization would be going an inverted way.<BR>
You know fractions of k digits and extend them by one digit.<BR> to be continued..
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/293854"