Sorting on chinese remainder theorem

[henryzz]

Could you store and sort the logarithm of the large numbers?

[xilman]

Originally Posted by alpertron

Is there any way to generate the 8 values of x (mod 7*13*37) sorted without having to generate all values of x using CRT and then sorting them?

Knuth, 4.3.2, especially Theorem S.

TL;DR: no.

[LaurV]

Originally Posted by alpertron

... because this is an application that runs inside a Web browser and the memory is limited. The problem is not the sorting time (calculating the modular values of x is more expensive), but the amount of memory.

[offtopic]
That is funny to hear, considering that my browser successfully grabs all the memory it can, letting my computer dressed like Adam and Eve, and running extremely slow, no mater what web pages I open, as soon as there are enough of them opened ....
(this is just a joke, the things are not so bad, really)
[/offtopic]

[alpertron]

Originally Posted by LaurV

[offtopic]
That is funny to hear, considering that my browser successfully grabs all the memory it can, letting my computer dressed like Adam and Eve, and running extremely slow, no mater what web pages I open, as soon as there are enough of them opened ....
(this is just a joke, the things are not so bad, really)
[/offtopic]

The problem is that we cannot use a lot of memory for an application residing in a particular tab. Furthermore, I want my applications to run on smartphones, which do not have a lot of memory when compared to desktops.

[science_man_88]

Originally Posted by alpertron

The problem is that we cannot use a lot of memory for an application residing in a particular tab. Furthermore, I want my applications to run on smartphones, which do not have a lot of memory when compared to desktops.

the real hard part, is finding any hard and fast rules to sort by. you can calculate things using addition and mod like this:


so we have the chain 3,9 mod 7 when we add mod 7 for the 13 case, and resulting in 13+3=16 mod the product of 7 and 13 which can be reduced to a addition loop. but that without being able to sort other things this doesn't help much ( though the thought to sort by different subsets of the conditions has popped into mind, I'm not sure it helps).

[xilman]

Originally Posted by science_man_88

the real hard part, is finding any hard and fast rules to sort by. you can calculate things using addition and mod like this:


so we have the chain 3,9 mod 7 when we add mod 7 for the 13 case, and resulting in 13+3=16 mod the product of 7 and 13 which can be reduced to a addition loop. but that without being able to sort other things this doesn't help much ( though the thought to sort by different subsets of the conditions has popped into mind, I'm not sure it helps).

Did you read the Knuth, the whole Knuth and nothing but the Knuth I suggested before posting the above?

I'm trying very hard not to go into a -like meltdown at this point

[science_man_88]

Originally Posted by xilman

Did you read the Knuth, the whole Knuth and nothing but the Knuth I suggested before posting the above?

I'm trying very hard not to go into a -like meltdown at this point

so ban me for a week, I can't even find the result you talk about using google.

[henryzz]

Originally Posted by science_man_88

so ban me for a week, I can't even find the result you talk about using google.

https://github.com/djtrack16/thyme/b...g.Volume.2.pdf

[chalsall]

Originally Posted by xilman

Did you read the Knuth, the whole Knuth and nothing but the Knuth I suggested before posting the above?

I still have Knuth's Metafont book in my library.

Damn that guy is funny!!!

Edit: I love how awkward he is. https://www.youtube.com/watch?v=zwp4kxhUgZU

[alpertron]

Originally Posted by xilman

Knuth, 4.3.2, especially Theorem S.

TL;DR: no.

I have read that threorem S but it is not applicable to this problem, because that theorem works when the values are represented as (a1 mod m1, a2 mod m2, a3 mod m3, etc).

In my case I can represent the values as a + b * b₁ + c * c₁ + d * d₁ + ... (mod m), where b₁, c₁, d₁, etc. can equal zero or one so only a few CRTs are required in my case to determine a, b, c, d, etc.

[chalsall]

Originally Posted by alpertron

In my case I can represent the values as a + b * b₁ + c * c₁ + d * d₁ + ... (mod m), where b₁, c₁, d₁, etc. can equal zero or one so only a few CRTs are required in my case to determine a, b, c, d, etc.

So that suggests an optimization is possible.

Any success with that yet?