Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Topic:
Another count sort that certainly must exist, it do not have any restrictions upon size of (S number of possibilities)
Replies:
11
Last Post:
Jan 8, 2013 1:37 AM



JT
Posts:
1,388
Registered:
4/7/12


Re: Another count sort that certainly must exist, it do not have any restrictions upon size of (S number of possibilities)
Posted:
Jan 4, 2013 8:29 PM


On 4 Jan, 18:07, David Bernier <david...@videotron.ca> wrote: > On 01/04/2013 10:46 AM, JT wrote: > > > > > > > > > > > On 4 Jan, 15:46, JT<jonas.thornv...@gmail.com> wrote: > >> I remember doing this in a tentamen during my education in information > >> theory beleiving what i did was binary sort but my teacher informed me > >> it wasn't so what is it. > >> By creating a Pascal pointer binary tree with each leaf holding a > >> integer, you move the binary numbers to the tree from least digit to > >> highest using left legs for 0's and right for 1's. (Basicly creating > >> leaves for new numbers, and at last digit you add 1 to the leaf slot. > >> So after you moved all values into the tree and created all the nodes, > >> you simply read out all the none zero values holded into the slot of > >> the leaves within the binary tree. > > >> What is this sort called? > >> Of course you cannot have more leaves then memory, but this does not > >> need to hold memory for slots never used like the array slots, it is > >> therefore my beleif that this sort could be useful also for database > >> purposes sorting basicly anything. What do you think? > > > I can see there would be problems reading out the sizes of a binary > > tree from smallest to biggest, if you have legs with different > > lengths? Is there any algorithmic solution to this problem. > > I have kind of a foul play solution, you create a binary tree for > > every digit bigger then 2^20 the smaller ones you run with the array > > approach. So for 21,22,23... bits and so on each numbers run on their > > own computers, with 2048 computers you could sort enormous amount of > > data of different size. So basicly the "heaps?" all have legs with > > same sizes and is easy to read out in order. > > Is this a working idea or just plain silly, maybe it is just easier to > > use one computer and read out the values from the heap and sort them > > with quicksort after you filled up the tree? (Is it called tree or > > heap, what is the difference betwee a heap and a tree?). > > > So what you think about the mix using this kind of sort for counting > > in values, and then quicksort to sort the none null tree nodes by > > sizes. > > Oops.. below is about factoring. The best algorithms > have been getting better since Maurice Kraitchik's [1920s] > improvement on Fermat's method of expressing a number > as a difference of squares, n = a^2  b^2, so > n = (ab) (a+b). > > There's a very good article called "A Tale of Two Sieves" > by Carl Pomerance: Notices of the AMS, vol. 43, no. 12, > December 1996: > <http://www.ams.org/notices/199612/index.html> > > The 9th Fermat number F_9 = 2^(512)+1 had been factored > around 1990 by the Lenstras et al using the Number Field > sieve (which had supplanted the quadratic sieve). > > The Quadratic sieve is easier to understand than the > Number Field Sieve, which I don't understand. > > F_10 and F_11 were fully factored then, using the elliptic > curve method (which can find smallish prime factors). > > F_12 was listed as not completely factored, with > F_12 being a product of 5 distinct odd primes and > the 1187digit composite: > > C_1187 = > 22964766349327374158394934836882729742175302138572\ > 22257593176439130841895160961323826592803808643123\ > 15776330453915314460450194556572637889591520959595\ > 00781101126096495656976145338084323609391242570049\ > 59146146100932078255130896682422242552873156911153\ > 49491277441664272360127694182069497019299146312879\ > 53679124328078403443589001544785043209243005176672\ > 36512498567556601129618233580642646148465607080211\ > 50483896593552361820682419503442019994498256473415\ > 56766313684295383743697537161298411893329950259437\ > 02457251084955979786901113201153080673107947314499\ > 89885761657097352227077484815352368256239445951125\ > 33741234160090993221997405711848497115626313770615\ > 84634017936609811822404415794282448107580150138831\ > 67949250345497227202182371779894151535731419443909\ > 33701532957472310726727304029461192020120667119324\ > 40906462375814643855500503626564314311613740004222\ > 88239457400101057642788560965414596506825478363862\ > 10032027169896230115182649724551245475912070548418\ > 45921140740300676916471986974995922243980616471547\ > 01759458614628952014532145179607626863555620392963\ > 07129357252744645128034273466002900209575716007479\ > 66912966168394403107609922082657201649660373439896\ > 3042158832323677881589363722322001921. > > At 3942 bits for C_1187 above, what's the > probability density function of expected time > till C_1187 is fully factored? > > Or, centiles: e.g. 50% chance fully factored > within <= 10 years. 95% chance fully factored within > <= 95 years, etc. ... > > dave
Is this idea the same sort as the other counting sort, it seem more adjustable to sort anysized number when just fitting them into the binary tree.



