|
||
|
Title: Looking for a better computational technique Post by BenVitale on Jan 21st, 2010, 5:22pm I'm looking for a better computational technique My question: How to count the size of a large group as quickly as possible? We could use the Chinese Remainder Theorem However, there are some limitations to this approach, since it cannot tell us exactly the size of that large group I'm interested in finding ways of counting a large group of unknown size. Is there a better technique than the chinese remainder theorem to determine the size of a group? We could be counting, for example, a very large number N of pennies in jars or other containers ... as shown in this example: Using Grouping to Count Quickly (http://www.teachersdomain.org/resource/vtl07.math.number.nums.countquick/) Or, we could be interested in counting quickly the size of a very large crowd of people. If the size is 10,000, I figure we could use the 7-11-13 remainder method for larger numbers. And if the number N is much larger, then we determine the remainder after dividing by each member of a sequence of prime numbers, say 2, 3, 5, 7, 11, 13, 17, 19. A generalization of this problem would be: Let N represent the total size of the crowd or group of people. Let r1 be the remaining number of people when asked to form groups of size p1. Let r2 be the remaining number of people when asked to form groups of size p2. If r1 and r2 are relatively prime, the CRT says that the remaining number of people left over when groups of size p1 * p2 are formed is calculated using the following (r1 * p2 * x1 + r2 * p1 * x2) mod(p1 * p2) with x1 = (p2)-1 mod(p2) and x2 = (p1)-1 (mod(p2) Which other computational technique would be better than the CRT with this kind of problem? I mean a better technique that could tell us what N is with certainty[/quote] |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |