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



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 9:47 PM


On 01/04/2013 08:29 PM, JT wrote: > 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.
I gave a reply that should have been in reply to your question about the complexity of factoring integers.
The most important ideas for the quadratic sieve [for factoring] are not related to sorting algorithms.
Sorting algorithms are well analyzed in Knuth's tomes. I forgot the title of the series of two to three tomes.
dave



