h a l f b a k e r yNumber one on the no-fly list
add, search, annotate, link, view, overview, recent, by name, random
news, help, about, links, report a problem
browse anonymously,
or get an account
and write.
register,
|
|
|
Please log in.
Before you can vote, you need to register.
Please log in or create an account.
|
The theory is that a logic circuit whose signals flow in a closed loop, will automatically find the combination of logic levels for all of its gates which produces no logical conflicts, where such a combination exists. In a real logic circuit, when there is a logical conflict, it tends to oscillate (try
connecting the output of an inverter to its input). In a circuit as complex as this is likely to be, there will probably be brief internal conflicts as it tries to make a decision. Even brief conflicts could send the circuit into endless oscillation even when there is a solution to the problem it's been given to solve. To avoid this, one could apply the signals which define its problem while the circuit's power is off, then gradually increase power to normal over 0.1 to several seconds.
See the link to the illustration, or this article won't make much sense to you. The circuit in the drawing is not expected to work as is, but it's about as close as I've been able to get.
The device is a logic circuit with its output values (factors) fed back into its inputs. It consists mainly of four functional units: a multiplier, a comparer and two dividers.
The multiplier feeds the comparer, which in turn feeds both dividers. The need for two dividers will be explained later.
A vital part of the circuit which is not shown, is the "Anti 1 Divisor", which prevents generation of the useless factor "1".
The number to be factored goes to the comparer. The comparer's other input comes from the multiplier.
The output of the comparer, which always equals the input number, goes to one input of each of the two dividers.
The output of each divider has three destinations:
(1) The divisor input of the other divider.
(2) One input of the multiplier.
(3) One output of the factoring circuit.
The comparer is needed to impress the input number onto the circuit without interfering directly with the logic loop. It allows the input number to influence the signals in the logic loop.
The reason two dividers are needed, is so that each one can send its output divisor to the other. Without this, there wouldn't be enough internal feedback in the loop to discriminate against invalid divisors.
One more vital aspect of this is that the entire circuit, including the functional units (multiplier, comparer and dividers) must operate in a single step from start to finish --- a continuous, complex chain of logic signals. This means that it can't use an ALU (Arithmetic / Logic Unit) which performs calculations in multiple steps.
All outputs should be checked with an ordinary CPU, since the output for a prime number is so far undefined. A prime number couldn't yield a logical output, so the circuit would probably just oscillate as it continued the hopeless task of trying to factor it.
I'm not sure there are any "one-step" multiplier or divider circuits, so to test the concept of logic circuits with internal feedback, one could first make one which finds pairs of numbers whose sums equal the input number. If that is successful, one could begin considering the challenge of one-step multipliers and dividers. There might even be a way to use multi-step multipliers and dividers, but it doesn't seem likely.
Factoring Circuit
http://s24.postimg....2lipjtcl/Factor.gif
Factoring circuit drawing [Alvin, May 23 2013]
A/D converter
http://www.ktclear....d%20AD%20Converters
[piluso, May 23 2013]
[link]
|
| |
It may be worth considering a simple test like "4",
and drawing the state of the circuit at successive
very short intervals. |
|
| |
I'm not sure what your comparator is doing, as you
say its output is always equal to its input (I
presume
you mean the upper input, which is the number
you
want to factorize). If this is so, then the
comparator
is merely a buffer and can be omitted. |
|
| |
If you can clarify this point (ie, what the
comparator is actually doing), I can maybe
implement this in LabView and see what it does. |
|
| |
You will have problems knowing when you can sample the output, even if you manage to invent one-step multipliers and dividers. |
|
| |
The other problem is of course that you only have two outputs. |
|
| |
so for e.g. an input of 30, will your circuit eventually settle to one of 2*15, 5*6, 3*10 randomly, or just oscillate between valid solutions forever? |
|
| |
When people want a faster way to factor numbers, they are usually referring to finding all the prime factors. |
|
| |
This resembles an A/D converter [link] where a counter evolves until the comparator finds an aproximation to the input value. |
|
| |
//a counter evolves until the comparator finds an
aproximation to the input value.// Sort of, but it's
not a problem that admits of optimisation. For
example, if you're factoring 437, 6x73 gives nearly
the right answer, but the factors are not close to
being 6 and 73. |
|
| |
MaxwellBuchanan,
The comparator is intended to provide a way to influence the circuit with the signals from the input number. It supposed to help it focus on the given problem. Without it, the circuit would pick a number at random and factor it instead.
As stated, the circuit as drawn isn't likely to work, but it's as close as I could get.
(Added later)
By the way, I had originally meant it to be a mathematical "comparer" not "comparator", but on second thought it shouldn't make any difference. |
|
| |
prufrax,
One could know a solution was ready when the output signals were stable for more than the inherent oscillation time of the circuit.
You're right about the lack of support for multiple pairs of factors. For those it would probably pick a pair at random and stick to them. |
|
| |
So, isn't this just a random number generator that
stops when it hits the right answer? |
|
| |
bigsleep,
//So back to software factoring then.//
With software, it's much easier to verify that two numbers are factors of another number than to factor the number of interest. It's one step versus sqrt(n) steps. |
|
| |
bigsleep,
The comparator is the only thing I could think of that might get the circuit to favor choosing the number of interest as the one to factor. Otherwise it would pick one at random and factor it instead.
Oscillation is just an expected potential consequence of logic loops. It isn't an intentional or preferrable part of its operation.
|
|
| |
Lots of interesting sub-issues here which are intereting to think about, but the big issue is with your initial assumption: |
|
| |
// logic circuit whose signals flow in a closed loop, will automatically find the combination of logic levels for all of its gates which produces no logical conflicts, where such a combination exists // |
|
| |
// To avoid this [oscillaition], one could apply the signals which define its problem while the circuit's power is off, then gradually increase power to normal over 0.1 to several seconds // |
|
| |
I completely agree that you could create a circuit that would not be stable unless the output was two factors of the input. And you are correct that it would tend to oscillate. I think the fatal flaw is assuming that powering it on gradually will somehow make it possible to come up with the correct state. |
|
| |
If the supply voltage for a digital circuit is just a little low, all the gates maintain their proper function, but the propogation speed is reduced. As the voltage continues to drop, the basic function of the gates break down to the point where the output of each gate depends more on the matching of transisitors in the gate than on the input. So starting at 0 voltage, the nodes between gates will all be at random voltages. As the voltage rises, some gates will start to function first and drive a 1 or 0. As other gates come online, they will either change the input of the gates that are already functioning, causing htem to switch, and/or set their output based on input from already fiunctioning gates. You won't have any feedback through the whole circuit that would help find your solution until the point that all the gates are functioning, but as soon as you get all the gates functioning, you will be getting oscillations as it searches for a stable state. So turing it on slowly vs. rapidly only has the affect of changing the initial strate, but that initial state is not any more likely to be the stable state that would give you your answer. |
|
| |