Sitat av
m0b
Første implementasjon for luke 2.
Kode
#include <iostream>
#include <chrono>
#include <cmath>
int main()
{
auto begin = std::chrono::high_resolution_clock::now();
double i, sum, fib, run;
for (run = 0; run < 5e6; run++)
{
for (i = sum = fib = 0; fib < 13e8; sum += ((int)fib & 1) ? fib : 0, (fib = floor(pow((1 + sqrt(5)) / 2, i++) / sqrt(5) + 0.5)));
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count();
std::cout << "+ " << sum << std::endl;
std::cout << (i*run) << " iterations run in " << (double)duration << "ns total, average : " << duration / (i*run) << "ns." << std::endl;
return 0;
}
Kode
+ 1.48561e+09
2.35e+08 iterations run in 8.17514e+09ns total, average : 34.7878ns.
Nå vekker jeg til live igjen en fire år gammel tråd, og beklager forsåvidt det, men jeg har ikke hatt helt fred i meg siden denne oppgaven. Var ganske sikker på at det var en løsning der ute som ville tillate meg å løse denne oppgaven uten for-loops, rekusjon, de mest normale kjente metodene og ikke minst konstant tid uavhengig av problemstørrelse. Har tidvis vært innom denne oppgaven innimellom for å finne metoder. Her bygger jeg videre på binet's formel som jeg brukte i første implementasjon og utnytter videre matriseform for å kjapt kalkulere det n-te tallet, samt at summen av n partall og n oddetall skal være lik.
Så jeg presenterer herved andre implementasjon for luke 2!
Kode
namespace fibs
{
using System;
using System.Text;
using MathNet.Numerics.LinearAlgebra.Double;
class Program
{
static void Main(string[] args)
{
Console.WriteLine(@"Fibonaccirekken er en tallrekke som genereres ved at man adderer de to foregående tallene i rekken. f.eks. om man starter med 1 og 2 blir de første 10 termene 1, 1, 2, 3, 5, 8, 13, 21, 34 og 55
Finn summen av alle partall i denne rekken som er mindre enn 4.000.000.000" + Environment.NewLine);
var limit = 4e9;
var phi = (1 + Math.Sqrt(5)) * 0.5;
var nth = (int)Math.Floor((Math.Log(limit + 0.5) + (0.5 * Math.Log(5))) / Math.Log(phi));
var m0 = DenseMatrix.OfArray(new[,] { { 1.0, 1.0 }, { 1.0, 0.0 } });
var m1 = m0.Power(nth + 1);
var fib = m1[1, 1];
Console.WriteLine($"Fibonacci-tall nr. {nth} er {fib}, og summen av alle fibonacci partall opp til {limit}, er {(fib - 1) * 0.5}.");
}
}
}
Fibonaccirekken er en tallrekke som genereres ved at man adderer de to foregående tallene i rekken. f.eks. om man starter med 1 og 2 blir de første 10 termene 1, 1, 2, 3, 5, 8, 13, 21, 34 og 55
Finn summen av alle partall i denne rekken som er mindre enn 4.000.000.000
Fibonacci-tall nr. 47 er 2971215073, og summen av alle fibonacci partall opp til 4000000000, er 1485607536
Fibonacci-tall nr. n finner en også slik med binet's formel om man ikke ønsker bruke matriseform:
Kode
var limit = 4e9;
var phi = (1 + Math.Sqrt(5)) * 0.5;
var nth = (int)Math.Floor((Math.Log(limit + 0.5) + (0.5 * Math.Log(5))) / Math.Log(phi));
var fib = Math.Floor(Math.Pow(phi, nth) / Math.Sqrt(5) + 0.5);
var sum = (fib - 1) * 0.5;
Alternativt
Kode
var fib = Math.Floor(Math.Exp(nth * Math.Log(phi)) / Math.Sqrt(5) + 0.5);
var sum = (fib - 1) * 0.5;
Kan også for ordensskyld nevne at jeg tidligere har forsøkt med en annen optimalisering. Nemlig å benytte
SIMD, men her mister jeg presisjon etter rundt 100 iterasjoner. Her har jeg også benchmarks (med både doubles og floats) med for å se den potensielle tidsoptimaliseringa fra første implementasjon.
Kode
namespace fibs
{
using System;
using System.Diagnostics;
using System.Numerics;
using BenchmarkDotNet.Attributes;
public class BenchmarkComputation<T>
{
public Action<T[], int> ComputeMultiple;
public Action<T[], int> ComputeSingle;
}
public class Benchmark
{
readonly double phi_d = (1 + Math.Sqrt(5)) * 0.5;
readonly float phi_f = (1 + MathF.Sqrt(5)) * 0.5f;
int index, vecSize, numFibs = 1000;
double[] doubles;
float[] floats;
BenchmarkComputation<double> computation_d;
BenchmarkComputation<float> computation_f;
public Benchmark()
{
doubles = new double[numFibs];
computation_d = new BenchmarkComputation<double>();
computation_d.ComputeMultiple = (numbers, index) => Compute4n_d(index).CopyTo(numbers, index);
computation_d.ComputeSingle = (numbers, index) => numbers[index] = ComputeN_dexp(index);
floats = new float[numFibs];
computation_f = new BenchmarkComputation<float>();
computation_f.ComputeMultiple = (numbers, index) => Compute8n_f(index).CopyTo(numbers, index);
computation_f.ComputeSingle = (numbers, index) => numbers[index] = ComputeN_fexp(index);
}
[Benchmark]
[Arguments(10)]
public double ComputeN_d(double n) => Math.Floor(Math.Pow(phi_d, n) / Math.Sqrt(5) + 0.5);
[Benchmark]
[Arguments(10)]
public float ComputeN_f(float n) => MathF.Floor(MathF.Pow(phi_f, n) / MathF.Sqrt(5) + 0.5f);
[Benchmark]
[Arguments(10)]
public float ComputeN_fexp(float n) => MathF.Floor(MathF.Exp(n * MathF.Log(phi_f)) / MathF.Sqrt(5) + 0.5f);
[Benchmark]
[Arguments(10)]
public double ComputeN_dexp(double n) => Math.Floor(Math.Exp(n * Math.Log(phi_d)) / Math.Sqrt(5) + 0.5);
[Benchmark]
[Arguments(10)]
public Vector<double> Compute4n_d(double n) => new Vector<double>(new double[] {
ComputeN_dexp(n),
ComputeN_dexp(n + 1),
ComputeN_dexp(n + 2),
ComputeN_dexp(n + 3)
});
[Benchmark]
[Arguments(10)]
public Vector<float> Compute8n_f(float n) => new Vector<float>(new float[] {
ComputeN_fexp(n),
ComputeN_fexp(n + 1),
ComputeN_fexp(n + 2),
ComputeN_fexp(n + 3),
ComputeN_fexp(n + 4),
ComputeN_fexp(n + 5),
ComputeN_fexp(n + 6),
ComputeN_fexp(n + 7)
});
[Benchmark]
public double[] RunDoubles()
{
vecSize = Vector<double>.Count;
for (; index < numFibs - vecSize + 1; index += vecSize)
{
Compute4n_d(index).CopyTo(doubles, index);
}
while (index != numFibs)
{
doubles[index++] = ComputeN_dexp(index);
}
index = 0;
return doubles;
}
[Benchmark]
public float[] RunFloats()
{
vecSize = Vector<float>.Count;
for (; index < numFibs - vecSize + 1; index += vecSize)
{
Compute8n_f(index).CopyTo(floats, index);
}
while (index != numFibs)
{
floats[index++] = ComputeN_fexp(index);
}
index = 0;
return floats;
}
[Benchmark]
public double[] RunGenericDoubles()
{
vecSize = Vector<double>.Count;
for (; index < numFibs - vecSize + 1; index += vecSize)
{
computation_d.ComputeMultiple(doubles, index);
}
while (index != numFibs)
{
computation_d.ComputeSingle(doubles, index++);
}
index = 0;
return doubles;
}
[Benchmark]
public float[] RunGenericFloats()
{
vecSize = Vector<float>.Count;
for (; index < numFibs - vecSize + 1; index += vecSize)
{
computation_f.ComputeMultiple(floats, index);
}
while (index != numFibs)
{
computation_f.ComputeSingle(floats, index++);
}
index = 0;
return floats;
}
}
}
Kode
Method n Mean Error StdDev
ComputeN_d 10 27.57 ns 0.6113 ns 0.5419 ns
ComputeN_f 10 11.28 ns 0.2628 ns 0.2459 ns
ComputeN_fexp 10 14.41 ns 0.3311 ns 0.3400 ns
ComputeN_dexp 10 17.67 ns 0.3013 ns 0.2818 ns
Compute4n_d 10 76.58 ns 1.4503 ns 1.3566 ns
Compute8n_f 10 117.08 ns 2.3343 ns 2.4977 ns
RunDoubles ? 20,228.82 ns 475.3984 ns 711.5539 ns
RunFloats ? 48,781.02 ns 952.1425 ns 1,096.4888 ns
RunGenericDoubles ? 22,229.58 ns 192.6551 ns 160.8757 ns
RunGenericFloats ? 49,733.11 ns 966.6905 ns 992.7200 ns
Sist endret av m0b; 17. november 2020 kl. 01:33.