|
|
 | | From: | Tachyon | | Subject: | best factors | | Date: | Sun, 23 Jan 2005 23:40:06 +0000 (UTC) |
|
|
 | I have the following problem:
Given a target number from 500,000 to 4,000,000, I'm
tasked with finding two factors which minimize:
err = | x*y - target |
where 65535>=x>=1000 and 1000>=y>=16
The catch is, I'm doing this in an 8-bit microcontroller,
and I'd like to do it was quickly and elegantly as possible.
I have a time budget of about 1ms, so a brute force method
is out of the question.
I have modeled and simulated one
simple technique, in which the floor and ceiling of the square
root of the target are considered as candidates. This is
quick enough, but the accuracy is, worst case 0.07%, which is not
acceptable. I'd like at least an order of magnitude (in base 10)
better. Does anyone know if this happens to belong to a
class of well-known problems? I've done some scraping
on the net, can't find anything yet.
--
different MP3 every day! http://gweep.net/~shifty/snackmaster
. . . . . . . . ... . . . . . .
"Anything moving in the zone, even a three-year- | Niente
old, needs to be killed." -Captain R. |
|
|
| | From: | Allan Herriman | | Subject: | Re: best factors | | Date: | Mon, 24 Jan 2005 16:47:08 +1100 |
|
|
| On Sun, 23 Jan 2005 23:40:06 +0000 (UTC), Tachyon
wrote:
>I have the following problem:
>
>Given a target number from 500,000 to 4,000,000, I'm
>tasked with finding two factors which minimize:
>err = | x*y - target |
>where 65535>=x>=1000 and 1000>=y>=16
>
>The catch is, I'm doing this in an 8-bit microcontroller,
>and I'd like to do it was quickly and elegantly as possible.
>I have a time budget of about 1ms, so a brute force method
>is out of the question.
>
>I have modeled and simulated one
>simple technique, in which the floor and ceiling of the square
>root of the target are considered as candidates. This is
>quick enough, but the accuracy is, worst case 0.07%, which is not
>acceptable. I'd like at least an order of magnitude (in base 10)
>better. Does anyone know if this happens to belong to a
>class of well-known problems? I've done some scraping
>on the net, can't find anything yet.
You could search for x and 1/y instead of x and y. That will enable
you to use a continued partial fraction expansion, such as one based
on Euclid's GCD algorithm.
My experience has been that this converges very rapidly (you will
probably only need 4-5 iterations), so it may meet your 1ms deadline.
I used to have a link to some C code, but I can't find it now.
Regards,
Allan
|
|
| | From: | Allan Herriman | | Subject: | Re: best factors | | Date: | Mon, 24 Jan 2005 17:39:45 +1100 |
|
|
| On Mon, 24 Jan 2005 16:47:08 +1100, Allan Herriman
wrote:
>On Sun, 23 Jan 2005 23:40:06 +0000 (UTC), Tachyon
> wrote:
>
>>I have the following problem:
>>
>>Given a target number from 500,000 to 4,000,000, I'm
>>tasked with finding two factors which minimize:
>>err = | x*y - target |
>>where 65535>=x>=1000 and 1000>=y>=16
>>
>>The catch is, I'm doing this in an 8-bit microcontroller,
>>and I'd like to do it was quickly and elegantly as possible.
>>I have a time budget of about 1ms, so a brute force method
>>is out of the question.
>>
>>I have modeled and simulated one
>>simple technique, in which the floor and ceiling of the square
>>root of the target are considered as candidates. This is
>>quick enough, but the accuracy is, worst case 0.07%, which is not
>>acceptable. I'd like at least an order of magnitude (in base 10)
>>better. Does anyone know if this happens to belong to a
>>class of well-known problems? I've done some scraping
>>on the net, can't find anything yet.
>
>
>You could search for x and 1/y instead of x and y. That will enable
>you to use a continued partial fraction expansion, such as one based
>on Euclid's GCD algorithm.
>
>My experience has been that this converges very rapidly (you will
>probably only need 4-5 iterations), so it may meet your 1ms deadline.
>
>I used to have a link to some C code, but I can't find it now.
.... but this would make 1/y an integer. I guess you want y to be an
integer.
Sorry,
Allan
|
|
|
