Sure thing. This problem happens to map to an FPGA really well because it can be expressed as shifts and masks. Here's pseudocode for a software implementation: search (mask, upper_int, num_ints_remaining) if num_ints_remaining == 0 then success! mask = mask | (mask << upper_int) | (mask >> upper_int) foreach i in [1,upper_int-1] such that mask[i] == 0 search(mask, i, num_ints_remaining - 1) find_best () foreach i in [1, infinity) search(1, i, 8) mask is conceptually an infinite bitmask where the kth bit is mask[k] for k in (-inf,inf); of course it's not too hard to bound the actual number of bits required. The hardware implementation is nearly identical, with the depth-8 recursion replaced by eight copies of a search module connected in a row. FPGAs are definitely harder to program than CPUs. These days you're generally better off using GPUs to accelerate whatever problem you're working on, although Microsoft is doing some *very* interesting work on integrating FPGAs into their data centers ( https://www.microsoft.com/en-us/research/project/project-catapult/). I just happened to have a Stratix IV GX development board sitting on my desk, and when you have a hammer... J.P. On Fri, Sep 9, 2016 at 1:24 PM, <rcs@xmission.com> wrote:
Can you say more about how the FPGA is used? If I'm remembering the details correctly, Beeler & Ankeny used the DARPA "guest chip" facility in the early 80's to create a custom chip for solving a particular Ramsey-number-ish problem. I expected this area to grow, especially as FPGAs eliminated the DARPA dependency. But I haven't seen any more results using this idea. My own (very brief) experience is that FPGAs are hard to program.
Rich
---------- Quoting "J.P. Grossman" <jpg@alum.mit.edu>:
Minor update for an old thread... I ran a search and found that the
smallest n for which there exists a set of 9 integers in [1,n] with distinct subset sums is 161. I believe (correct me if I'm wrong) that this was previously conjectured but not known. It was already known that a solution exists for n = 161 ( {161, 160, 159, 157, 154, 148, 137, 117, 77}, constructed from the Conway-Guy sequence).
The search took about 30 minutes on an FPGA (I'm pretty sure this could be sped up by at least 10x with some additional work, but 30 minutes was fast enough).
J.P.
On Thu, Oct 4, 2012 at 7:22 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
This 1988 paper by one W. F. Lunnon shows that 84 is optimal:
Uh-huh ... must have been a clever fellow --- wonder what happened to him? WFL
On 10/4/12, Fred W. Helenius <fredh@ix.netcom.com> wrote:
On 10/3/2012 9:52 PM, Fred lunnon wrote:
Nice problem.
Can't answer 2) at this stage, though strongly suspect yes!
I'd have to agree.
My best so far non-P set of 8 is
{86,85,84,82,79,73,62,42}
Can anyone improve on 86?
This 1988 paper by one W. F. Lunnon shows that 84 is optimal:
http://www.ams.org/journals/mcom/1988-50-181/S0025-5718-1988 -0917837-5/
(The definition there omits "non-empty" and "disjoint", but that doesn't actually change the property: if two distinct overlapping subsets have the same sum, so do the disjoint subsets produced by removing their intersection.)
On 10/3/12, Victor Miller <victorsmiller@gmail.com> wrote:
Say that a finite set of integers, A, has *property P* is there are two non-empty disjoint subsets S and T of A, such that sum(S) = sum(T) (where sum(X) is the sum of the elements of X).
1) Show that every 10 element subset of {1,...,100} has property P (this is fairly easy). 2) Is it true that every 9 element subset of {1,...,100} has property P?
-- Fred W. Helenius fredh@ix.netcom.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun