Approximately 2^(n^2)-2^(2n)+2n as n increases.
On Mon, Aug 27, 2012 at 8:47 PM, Jim Bromer <[email protected]> wrote: > Approximately 2^(n^2)-2^(2n) - 2n as n increases? > > > On Mon, Aug 27, 2012 at 8:16 PM, Jim Bromer <[email protected]> wrote: >> Damn. >> Approximately 2^(n^2)-2^(2n) - n as n increases? >> >> >> On Mon, Aug 27, 2012 at 8:14 PM, Jim Bromer <[email protected]> wrote: >>> Approximately 2^(n^2)-2^(2n)-log(2)n as n increases? >>> >>> >>> On Mon, Aug 27, 2012 at 8:11 PM, Jim Bromer <[email protected]> wrote: >>>> 2^(n^2)-2^(2n)-log(e)n as n increases approximately? (That is just a >>>> guess. Something about the proportion of primes since the primes won't >>>> be detected.) >>>> Maybe. >>>> >>>> On Mon, Aug 27, 2012 at 8:07 PM, Jim Bromer <[email protected]> wrote: >>>>> That last messaged contained another error. >>>>> There are 2^(n^2) possible ways to fill the n^2 bits of the partial >>>>> products but there are 2^(2n) possible ways to do it with a >>>>> well-formed set (given a nXn bit multiplier). So the worse case is >>>>> that I might have to go through would be 2^(n^2)-2^(2n) trials before >>>>> I found a system that represented a number that could be factored. So >>>>> the conclusion is the same. >>>>> I think that is right - or at least it is getting closer to the ballpark. >>>>> Jim Bromer >>>>> >>>>> On Mon, Aug 27, 2012 at 7:44 PM, Jim Bromer <[email protected]> wrote: >>>>>> Ok the wheels are slipping but train is slowly getting up to steam. >>>>>> >>>>>> How many possible ways are there to set up the n^2 bits of the partial >>>>>> products? 2^(n^2). Only n^2 are well-formed. (This is for a nXn >>>>>> multiplication algorithm). So even if I had the dreamed of polynomial >>>>>> time solution to Boolean Satisfiabiity the worse case is that I might >>>>>> have to go through 2^(n^2)-n^2 trials before I got a factorization. >>>>>> >>>>>> So even though you do not have to make the multiplication algorithm >>>>>> reversible in order to derive a Boolean Formula that will detect a >>>>>> non-prime number (given a set of possible partial products), if the >>>>>> goal is to use the method with a polynomial time solution to Boolean >>>>>> Satisfiabilty then you are going to have to make it reversible (or >>>>>> something like that) if you are want to use it to find a factorization >>>>>> solution to any given number in polynomial time. >>>>>> >>>>>> Jim Bromer >>>>>> (I might be wrong...It has happened. I admit it.) >>>>>> >>>>>> >>>>>> >>>>>> On Mon, Aug 27, 2012 at 7:21 PM, Jim Bromer <[email protected]> wrote: >>>>>>> Unfortunately I was wrong about this, but the method does have a flaw. >>>>>>> >>>>>>> The partial products are fully specified in the sense that they detail >>>>>>> the relationships between each bit as it is used in the cross-products >>>>>>> in a consistent manner based on the bits of the multiplicand. So if >>>>>>> you had a Boolean Solver then the Boolean formula of the cross >>>>>>> products (derived from a standard multiplication algorithm) could be >>>>>>> used to determine if there was a solution for a given system of >>>>>>> cross-products. >>>>>>> >>>>>>> However, if the system detected that there was no solution to a >>>>>>> problem (given a system of partial products) it would not definitely >>>>>>> represent a prime number since the given system could be poorly >>>>>>> formed. On the other hand it should be able to detect a >>>>>>> factorization. If it found that a system could be factored based on >>>>>>> the fact that there was a solution to the Boolean Formula, then the >>>>>>> given system of partial products could be added to detect the number >>>>>>> that can be factored. >>>>>>> >>>>>>> Jim Bromer >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> On Mon, Aug 27, 2012 at 6:48 PM, Jim Bromer <[email protected]> wrote: >>>>>>>> I was really surprised when I discovered that converting the >>>>>>>> cross-products, used to determine the partial products, of a binary >>>>>>>> multiplication into the form of Boolean logic was logically simple. >>>>>>>> It turns out that the methodology of the multiplication problem, when >>>>>>>> you are given the multiplicands is simple just as the multiplication >>>>>>>> algorithm is simple. However, if you were to try to work backwards to >>>>>>>> use the partial products to try to determine the multiplicands the >>>>>>>> problem is much more difficult. It is simple as long as poorly formed >>>>>>>> partial products have been filtered out beforehand. The formalization >>>>>>>> of the problem, (expressed in pure Boolean form), is not quite so >>>>>>>> simple if the algorithm is supposed to detect or avoid poorly formed >>>>>>>> partial products. >>>>>>>> >>>>>>>> It took me a long time to figure this out so I won't be calling any of >>>>>>>> the other boys in this group slow anytime soon. So anyway, if you >>>>>>>> wanted to use the multiplication algorithm as a factorization >>>>>>>> algorithm you would have to work the algorithm backwards in order to >>>>>>>> determine the multiplicands given the product, or to determine the >>>>>>>> multiplicands given a system of partial products. The use of the >>>>>>>> partial products as the given isn't simple because if a bit in a >>>>>>>> partial product = 0 it could be because the corresponding bits in one >>>>>>>> or both of the multiplicands that produced the cross product were 0. >>>>>>>> That shows that there are three ways to explain a bit in a cross >>>>>>>> product that equals 0. On the other hand if the bit in the cross >>>>>>>> product was 1 then we would know that both bits were 1, which shows >>>>>>>> that there should be a reasonably "easy" way to define the Boolean >>>>>>>> Logic of the partial products so that it would only allow correctly >>>>>>>> formed partial products to get past the Boolean Formula. >>>>>>>> >>>>>>>> This reasoning shows how complicated turning an algorithm into a true >>>>>>>> Boolean Formula can be. First we start off with the standard >>>>>>>> multiplication algorithm, ok. But if you want to use that algorithm in >>>>>>>> an unconventional way, you have to make sure that the implicit >>>>>>>> relations are well-formed in the sense that the unconventional usage >>>>>>>> will not present the given values in an unacceptable poorly-formed >>>>>>>> way. So even if you want to consider the problem in purely abstract >>>>>>>> way -using only Boolean variables- you have to be prepared for >>>>>>>> unexpected effects when your claim jumps the conventional rails. >>>>>>>> >>>>>>>> If you want to take the conversion of a multiplication function into a >>>>>>>> pure (variable) Boolean form and then use it to detect a factorization >>>>>>>> given a solution to the derived Boolean Formula, the multiplication >>>>>>>> method would first have to be expressed as a reversible function. >>>>>>>> Jim Bromer ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-c97d2393 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-2484a968 Powered by Listbox: http://www.listbox.com
