Prev: 562758 Constantly updated Free COmputer and business portal 14
Next: Optimal Golomb Ruler to SAT
From: cplxphil on 25 Mar 2010 08:59
On Mar 25, 3:26 am, Thorsten Kiefer <i...(a)tokis-edv-service.de> wrote:
> Am Thu, 25 Mar 2010 08:21:11 +0100 schrieb Thorsten Kiefer:
>
> > Am Wed, 24 Mar 2010 17:54:53 -0700 (PDT) schrieb cplxphil:
>
> >> Nice program!  Are you going to publish the source?
>
> >> -Phil
>
> > of course !
>
> It's on the bottom of the page now.
>
> Thorsten

Sweet, this is very useful. Thanks for building this.

It doesn't seem to work for large numbers of bits, e.g. I couldn't get
it to work with 100 bits and 10^30...however, I'm sure that if I
tinker with the source a bit I'll be able to get it to work.

Thanks again.

-Phil
From: Thorsten Kiefer on 25 Mar 2010 10:12
cplxphil wrote:

> On Mar 25, 3:26 am, Thorsten Kiefer <i...(a)tokis-edv-service.de> wrote:
>> Am Thu, 25 Mar 2010 08:21:11 +0100 schrieb Thorsten Kiefer:
>>
>> > Am Wed, 24 Mar 2010 17:54:53 -0700 (PDT) schrieb cplxphil:
>>
>> >> Nice program!  Are you going to publish the source?
>>
>> >> -Phil
>>
>> > of course !
>>
>> It's on the bottom of the page now.
>>
>> Thorsten
>
> Sweet, this is very useful. Thanks for building this.
>
> It doesn't seem to work for large numbers of bits, e.g. I couldn't get
> it to work with 100 bits and 10^30...however, I'm sure that if I
> tinker with the source a bit I'll be able to get it to work.
>
> Thanks again.
>
> -Phil

You're welcome. Unfortunately a large number of bits leads to very very
large instances.
I got suggestions to use a more efficient multiplier.
But I didn't understand the other multipliers, and I still
doubt they would lead to smaller instances.

If you find an improvement , please drop me a mail.

-Thorsten

From: Daniel A. Jimenez on 26 Mar 2010 13:15
In article <4bab6f31$0$3298$6e1ede2f(a)read.cnntp.org>,
Thorsten Kiefer <cylinder(a)news.cnntp.org> wrote:
>cplxphil wrote:
>> Sweet, this is very useful. Thanks for building this.
>>
>> It doesn't seem to work for large numbers of bits, e.g. I couldn't get
>> it to work with 100 bits and 10^30...however, I'm sure that if I
>> tinker with the source a bit I'll be able to get it to work.
>>
>> Thanks again.
>>
>> -Phil
>
>You're welcome. Unfortunately a large number of bits leads to very very
>large instances.
>I got suggestions to use a more efficient multiplier.
>But I didn't understand the other multipliers, and I still
>doubt they would lead to smaller instances.
>
>If you find an improvement , please drop me a mail.

I've done this using a Karatsuba multiplier. It results in much smaller
instances than the grade-school algorithm. For example, for a 512x512
bit multiply, it results in an instance that's 55% smaller. For 1024x1024
the improvement goes up to 66%. Of course it was a pain to code.
--
Daniel Jimenez djimenez(a)cs.utexas.edu
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
From: Thorsten Kiefer on 26 Mar 2010 16:14
Am 26 Mar 2010 12:15:30 -0500 schrieb Daniel A. Jimenez:

> In article <4bab6f31$0$3298$6e1ede2f(a)read.cnntp.org>,
> Thorsten Kiefer <cylinder(a)news.cnntp.org> wrote:
>>cplxphil wrote:
>>> Sweet, this is very useful. Thanks for building this.
>>>
>>> It doesn't seem to work for large numbers of bits, e.g. I couldn't get
>>> it to work with 100 bits and 10^30...however, I'm sure that if I
>>> tinker with the source a bit I'll be able to get it to work.
>>>
>>> Thanks again.
>>>
>>> -Phil
>>
>>You're welcome. Unfortunately a large number of bits leads to very very
>>large instances.
>>I got suggestions to use a more efficient multiplier.
>>But I didn't understand the other multipliers, and I still
>>doubt they would lead to smaller instances.
>>
>>If you find an improvement , please drop me a mail.
>
> I've done this using a Karatsuba multiplier. It results in much smaller
> instances than the grade-school algorithm. For example, for a 512x512
> bit multiply, it results in an instance that's 55% smaller. For 1024x1024
> the improvement goes up to 66%. Of course it was a pain to code.

But the growth is still about O(n^2), right ?
n*log(n) would be cool :D
Nevertheless I congratulate you. I won't implement this - to prevent a
serious headache :D

Is it possible to do signed multiplication in SAT ? I just read something
about the Booth multiplication. Have you done this ? I need it for my next
project.

-Thorsten
From: Thorsten Kiefer on 26 Mar 2010 16:26
Am 26 Mar 2010 12:15:30 -0500 schrieb Daniel A. Jimenez:

> In article <4bab6f31$0$3298$6e1ede2f(a)read.cnntp.org>,
> Thorsten Kiefer <cylinder(a)news.cnntp.org> wrote:
>>cplxphil wrote:
>>> Sweet, this is very useful. Thanks for building this.
>>>
>>> It doesn't seem to work for large numbers of bits, e.g. I couldn't get
>>> it to work with 100 bits and 10^30...however, I'm sure that if I
>>> tinker with the source a bit I'll be able to get it to work.
>>>
>>> Thanks again.
>>>
>>> -Phil
>>
>>You're welcome. Unfortunately a large number of bits leads to very very
>>large instances.
>>I got suggestions to use a more efficient multiplier.
>>But I didn't understand the other multipliers, and I still
>>doubt they would lead to smaller instances.
>>
>>If you find an improvement , please drop me a mail.
>
> I've done this using a Karatsuba multiplier. It results in much smaller
> instances than the grade-school algorithm. For example, for a 512x512
> bit multiply, it results in an instance that's 55% smaller. For 1024x1024
> the improvement goes up to 66%. Of course it was a pain to code.

I looked up for the algorithm. It's not n^2 , it's n^log2(3).
not bad.
I guess it has the best efficency-overhead tradeoff.
The other multipliers would cause too much overhead.
First  |  Prev  | 
Pages: 1 2
Prev: 562758 Constantly updated Free COmputer and business portal 14
Next: Optimal Golomb Ruler to SAT