Tuesday, June 20, 2017

Compiling Nvidia 340.102 driver for Linux 4.11.x kernel

Further to the patch for compiling 340.102 driver on 4.10.x kernel, to compile for 4.11.x kernel, add the following patch on kernel/nv-drm.c too.

From:

static int nv_drm_unload(
    struct drm_device *dev
)

to

#if LINUX_VERSION_CODE < KERNEL_VERSION(4, 11, 0)
static int nv_drm_unload(
#else
static void nv_drm_unload(
#endif
    struct drm_device *dev
)

Saturday, June 17, 2017

A Java stream approach on testing triangular Fibonacci numbers

Read this interesting blog post on testing triangular Fibonacci numbers.  And I decided to implement a similar test in Java.

First, a Java Stream to produce triangular numbers.

    public static Stream<BigInteger> stream() {
        return Stream
            .iterate(
                BigInteger.ONE,
                i -> i.add(BigInteger.ONE))
            .map(i -> i.multiply(i.add(BigInteger.ONE)).divide(TWO));
    }

And a Stream for Fibonacci sequence.

    public static Stream<BigInteger> stream() {
        return Stream
            .iterate(
                new BigInteger[] { BigInteger.ONE, BigInteger.ONE },
                p -> new BigInteger[] { p[1], p[0].add(p[1]) })
            .map(p -> p[0]);
    }

Now, a simple and naive way to test for a triangular Fibonacci number is to loop the Fibonacci sequence while testing for the number's existence in the stream of triangular numbers.

        Iterator<BigInteger> fib = FibonacciNum.stream().limit(TEST_LIMIT).iterator();
        Iterator<BigInteger> tri = TriangularNum.stream().iterator();
     
        BigInteger t = tri.next();
     
        List<BigInteger> result = new ArrayList<BigInteger>();
     
        while (fib.hasNext()) {
            BigInteger f = fib.next();
            while (t.compareTo(f) <= 0) {
                if (t.equals(f)) {
                    result.add(t);
                }
                t = tri.next();
            }
        }

But since the Fibonacci sequence grows so quickly, it is a waste of CPU time to generate all those triangular numbers.  A quicker way is to ditch the triangular number stream and implement a test function for triangular number.  We then use that function to filter the Fibonacci stream.

        List<BigInteger> result = FibonacciNum
            .stream()
            .limit(TEST_LIMIT)
            .parallel()
            .filter(f -> TriangularNum.isTriangular(f))
            .distinct()
            .sorted()
            .collect(Collectors.toList());

Testing the first 70 Fibonacci numbers, the time diff between the two approaches is huge (24ms vs 4s).


And with the fast approach, on an i5 4210 machine, testing the first 50,000 Fibonacci numbers will take 93s.

See source below or on GitHub.