As you may have noticed, the search over ℚ(√2) (subfield 3) has started to slow down and waiting for results is like watching paint dry. At the current rate it will probably take over 10 years to finish that search. In the interest of making progress, I have decided to start the search over subfield ℚ(√-2). This is the 4th of 7 subfields for the set {2,5}. We will continue to process subfield 3 in parallel, but at least we will be able to maintain progress on other subfields for the overall goal of this project.

The hope is that I can find time this year to develop a GPU app that will help to speed up the search. Of course I've been saying this for years...

Good News. GPU Apps, i can't wait. :-))

I've recently been looking at a new-ish computer language: Julia. It has a pretty easy mathematical syntax (3 * a in FORTran can be 3a in Julia). It also has syntax for parallel processing and vector processing. Parallel can mean co-routines on a single core (helping I/O and CPU overlap), multi-core shared memory, or systems on a network. Vector processing can be using the vector instructions that the processor (especially x86) has, a video card (nVidia or Radeon), on-chip video (like AMD's APU or an Arm's DSP or whatever Intel calls their on-chip video). The parallel syntax is fairly non-invasive, and mainly gives the language hints that you're not going to go wild with pointer references, etc. By new, i mean that the current release is 0.5. While the language has a JVM, with garbage collection and Just-In-Time compiling, it also can compile to the bare metal, and has, as a goal, near-C performance. The C language has been the gold standard for performance since the 80s. It can also either call other languages like C, or be called by other languages. Perhaps there's no need to recode any BOINC interfaces. Anyway, i'm looking at it specifically because it's a higher level language, and it looks like it can produce video card code without having to learn or code in video card instructions. Perhaps a good fit for NumberFields.

So far, i've read the 645 page manual (available online or in PDF) and have written a couple tens-of-lines programs and gotten them to get correct results. One of these is the Collatz core (which is real simple). Julia has easy arbitrary precision arithmetic support (it's an integer type), which helps here.

http://julialang.org/

I personally have _no idea_ what math NumberFields uses. I'm not totally ignorant about discrete math, but I mostly studied continuous Calculus stuff. Perhaps there are users who would be interested in helping out. That could speed things up.

Stephen.

I hadn't heard of Julia. It sounds interesting. NumberFields uses the Pari library for several number theoretic functions. This has been the biggest stumbling block that people have run into trying to make a GPU app for this project; and the main reason I am hesitant to try myself. You infer that Julia may have issues with pointer references; as it turns out, Pari makes frequent use of pointers (one thing that makes it powerful is the global stack workspace that all functions have access to via pointers). So Julia may not play nice with Pari.

If anyone wants to attempt the GPU app, just let me know. But be forewarned, that many have tried before and were unsuccessful. This is not a trivial task.

The gold standard for raw speed back in the 80's and I think in the 90's too is assembler, designed and optimized for the platform it should run on. A couple of years ago I wrote a 3x+1 application using x86 assembler, the complete win32 executable was only around 4kbytes in size and awful fast, especially on older machines.

Unfortunately I don't know anything on the "subfield math" used here either. But if it needs a big and mysterious mathematical library (pari), it seems to be complicated.

Is this needed to handle very big integers only or which mathematical functions or operations are necessary?

Are there any explanations on the internet where a very small field is displayed, so that this field and the mathematics behind it can be fully understood?

The gold standard for raw speed back in the 80's and I think in the 90's too is assembler, designed and optimized for the platform it should run on. A couple of years ago I wrote a 3x+1 application using x86 assembler, the complete win32 executable was only around 4kbytes in size and awful fast, especially on older machines.

Unfortunately I don't know anything on the "subfield math" used here either. But if it needs a big and mysterious mathematical library (pari), it seems to be complicated.

Is this needed to handle very big integers only or which mathematical functions or operations are necessary?

Are there any explanations on the internet where a very small field is displayed, so that this field and the mathematics behind it can be fully understood?

To anyone with an undergraduate degree in math it would not be "mysterious". But the mathematics is not trivial either. Among other things, it computes polynomial discriminants, field discriminants, irreducibility, and number factorization. Anyone understanding the math could code up these things, but the pari library is very efficient at doing it and it has been extensively tested so you can be confident that there are no bugs in the code. You mentioned assembly- as it turns out pari uses platform dependent assembly for many of it's core functions.

Maybe it's language-related that it is hard to understand for me. If you have a german article about it or "real hard math" to run and see what it is doing, it could be easier.

If anybody could code these things without using the PARI library, I don't understand why anybody failed creating a GPU app. I aspect modern compilers come very close to the speed of a pure-assembler program, but some years ago this was different.

Not just anybody could do it though - they would need an understanding of the math. I think many of those who volunteered to help had more of a computer science background. One person came close - they actually got a hybrid CPU/GPU version working and it speeded things up by about 30%. If memory serves, it still used a CPU core to do the hard math (using Pari). For this reason we never implemented it in the project.

Are you able to fully explain the math?

Yes. But it would be very time consuming to try to explain it here. I would suggest Wikipedia; their explanation might be better than mine anyways. I listed the main topics above. You could start with the polynomial discriminant and build from there:
https://en.wikipedia.org/wiki/Discriminant

It is interesting, are you thought about double checking of the tasks. Many projects have double checking.

Or it is no need because of specific scientific needs that we have in this project?

Thanks.

I don't do double checking because that would mean the project would have to wait twice as long to complete a search. The most likely reason for someone returning a faulty result would be deliberate maliciousness; do you know of any studies that show what percentage of users do that? Most of the "cheaters" find ways to artificially increase their FLOPS and/or compute time (like running many VMs in parallel) without compromising the results themselves.

With that said, my combiner scripts have checks in place to flag suspicious results. It has flagged numerous results, which I then run again, but so far none of these have been fallacious.

Also, the algorithm itself has some built in redundancy in the sense that it finds about 100 times as many polynomial representatives as there are actual fields. The theorems that the algorithm uses guarantee that there exist polynomial representatives within certain coefficient bounds, these bounds are sufficiently large that it picks up the field 100 times (on average). As a side note, finding tighter bounds would be one way to speed up the algorithm, as this would reduce the search space.

In addition to all that, once a search is complete, there are relationships between the numbers of fields of various Galois groups. This would most likely detect a missing field. For example, the number of decic fields with Galois group 10T17 must be even. But like a parity bit, the check can fail if there are multiple errors.

WHOA, just saw the new informations from sf3 DS16. Holy, thats a lot of work.

I don't do double checking because that would mean the project would have to wait twice as long to complete a search. The most likely reason for someone returning a faulty result would be deliberate maliciousness; do you know of any studies that show what percentage of users do that? Most of the "cheaters" find ways to artificially increase their FLOPS and/or compute time (like running many VMs in parallel) without compromising the results themselves.

With that said, my combiner scripts have checks in place to flag suspicious results. It has flagged numerous results, which I then run again, but so far none of these have been fallacious.

Also, the algorithm itself has some built in redundancy in the sense that it finds about 100 times as many polynomial representatives as there are actual fields. The theorems that the algorithm uses guarantee that there exist polynomial representatives within certain coefficient bounds, these bounds are sufficiently large that it picks up the field 100 times (on average). As a side note, finding tighter bounds would be one way to speed up the algorithm, as this would reduce the search space.

In addition to all that, once a search is complete, there are relationships between the numbers of fields of various Galois groups. This would most likely detect a missing field. For example, the number of decic fields with Galois group 10T17 must be even. But like a parity bit, the check can fail if there are multiple errors.

So do you mean that it is impossible for an incorrect result to be accepted for the project?

If a field is returned that is "incorrect", my combiner script will catch that.
It also has ways to detect when a field is missing from the data.

If my understanding were correct it's like doing probabilistic primality test - the chance of getting it wrong decrease exponentially with the number of trials. Getting error of it is not impossible but virtually impossible.

Are there any plans for numberfields@home, or any BOINC project for that matter, to add GPU support for integrated GPUs instead of exclusively AMD and Nvidia dedicated GPUs. It seems like an untapped resource.

I don't know about other projects, but my plan is to start by programming apps using Cuda/openCL first. I don't know enough about GPUs to know if the code is easily modified for integrated GPUs.

As far as I know newer integrated processors from Intel and AMD APUs support opencl, but then coding for them compared to dedicated processors may be more difficult. SETI is one project that provides work units for integrated GPUs due to the recent addition of opencl 1.2+ support, but then again it would benefit them more than other projects due to their size. It's worth a thought though in my opinion, any additional resources is a plus.

Looking Forward to try the GPU app.