labview challenge

[BruceAmmons]

Arrrgggghhhh!!!!

I have been doing all my development in LV 7.0, and I just tested it in LV 7.1. It turns out that the convolution vi has been changed, and the accuracy is not nearly as good as it once was. I don't know if it is a bug or not, but it made a mess of my solution. I finally ended up switching it to the Direct method instead of Frequency Domain, and everything works fine.

So, if anybody is using convolution, watch out for rounding errors that are new in LV 7.1. If you are running my old factorial program in LV 7.1, the results may not be correct due to the rounding errors in the new convolution vi.

Bruce

[Ben]

You do have a new avenue available to you now.


Ben

[altenbach]

You should get about the same speed using classic circular convolution with fourier transforms and maybe the precision is better. Have you tried?

I did not test 7.0 vs. 7.1, but I observed long ago that the number of "good" digits depends quite a bit on the array sizes, and array sizes that are integer powers of two are significantly better in general (using circular convolution). So it is worth padding the arrays, there is typically no speed penalty.

I haven't had any time to do much for the challenge yet, but maybe I get something ready. We'll see. 🙂

[BruceAmmons]

Putting together all the parts (FFT, inverse FFT, etc.) in LV 7 wasn't as fast as the built in convolution.

I did figure it out. If the size of the output array has prime factors larger than 5, the errors are significant. The worst one was 43, which made very large errors. I wrote a workaround that checks the size of the input arrays and adjusts them to total a value with only the prime factors 2, 3, and 5 plus one. I don't think the speed improvement would be significant over using the direct method of the convolution, so I will probably just stick with that.

Bruce

[altenbach]

I did not see this mentioned, but the results to the n'th root challenge have been posted. (when did that happen??)

🙂 😄 Congratulations  Franz Ahlers for the well deserved win!!!! 🙂 😄

Do you plan to share some of the winning code with us?

[BruceAmmons]

Congratulations Franz!!!  Excellent job on a difficult challenge.

For those that are interested, I have attached my best effort.

Bruce

[alkazaa]

Thanks!

Yes, I will upload my code, but I since I have no access to my home PC for the next weeks it may take some time. (Actually, I thought that NI would make the code available on the results page, as they had done it in the past).

It is probably not too interesting to look at my code, anyway, since Bruce Ammons solution is so much faster, and I only won since he was not in the judging. Bruce, if you read this: Could you please post your solution in LV 7.0, since I have no access to 7.1 at the moment?

To add to what was said on the results page already:

I used FFT and inverse FFT for the bigint multiply, not the convolution VIs. I also limited the precision of intermediate results, since the Newton iteration typically doubles the number of valid digits in each step and there is no need to calculate more digits than a given iteration step will produce. Starting with an initial value obtained by EXT floating point math, I have typically 14..15 digits of precision initially, which is 3 'digits' in the chosen 10^5 base. One obtains 3*2^i 'digits' after iteration step i.  For a 10000 digit decimal number (2000 'digits' in 10^5 base), the square root has 1000 'digits' and should be obtained after 9 iterations (3*2^8<1000, but 3*2^9 > 1000).

I'd really like to see what makes Bruce's solution 15 times faster, since I did not see much where I could speed up my code.

greetings from Taos, New Mexico

Franz

[BruceAmmons]

Here is my solution in LV7.

I just found a minor bug - it doesn't appear to work properly with very short numbers, such as the square root of 121.  I must have truncated too many digits in this case.

I think I used long division to calculate the new delta X, where Franz inverted the number then multiplied.  Otherwise, I think our approaches were very similar.

I just didn't feel it was fair for me to enter the competition.  I didn't start programming it until the challenge was announced, but I suggested it about 1 year earlier and had that time for it to perculate through my brain.

Bruce