Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

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

 Messages: [ Previous | Next ]
 David Bernier Posts: 3,662 Registered: 12/13/04
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 12:07 PM

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 = (a-b) (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

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 1187-digit 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

Date Subject Author
1/4/13 JT
1/4/13 JT
1/4/13 JT
1/4/13 David Bernier
1/4/13 JT
1/4/13 David Bernier
1/4/13 David Bernier
1/4/13 JT
1/4/13 JT
1/4/13 David Bernier
1/8/13 kiru.sengal@gmail.com
1/8/13 JT