Here is my implementation of a lock-free thread-safe Fibonacci number generator. Is it correct? The idea is to use an immutable holder for previous and current numbers (since it's hard to change two values atomically at the same time) and AtomicReference which points to the current Fibonacci number.Lock-freepublic class FibonacciSequence {    private static class FibonacciNumber {        protected final BigInteger prev;        protected final BigInteger curr;        public FibonacciNumber(BigInteger prev, BigInteger curr) {            this.prev = prev;            this.curr = curr;        }        public FibonacciNumber next() {            return new FibonacciNumber(curr, prev.add(curr));        }        public BigInteger value() {            return curr;        }    }    private static final class FirstFibonacciNumber extends FibonacciNumber {        public FirstFibonacciNumber() {            super(null, BigInteger.valueOf(0L));        }        public FibonacciNumber next() {            return new FibonacciNumber(curr, BigInteger.valueOf(1L));        }    }    private final AtomicReference<FibonacciNumber> currentFibNumberRef;    public FibonacciSequence() {        currentFibNumberRef = new AtomicReference<>(new FirstFibonacciNumber());    }    public BigInteger next() {        while (true) {            FibonacciNumber currFibNumber = currentFibNumberRef.get();            if (currentFibNumberRef.compareAndSet(currFibNumber, currFibNumber.next()))                return currFibNumber.value();        }    }Testing    public static void main(String[] args) {        testFibonacciNumberCorrectness();        // todo add thread-safe test    }    private static void testFibonacciNumberCorrectness() {        int[] some = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,                       233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,                       17711, 28657, 46368, 75025, 121393, 196418, 317811};        FibonacciNumber currFibNumber = new FirstFibonacciNumber();        for (int num : some) {            assert num == currFibNumber.value().intValue();            currFibNumber = currFibNumber.next();        }    }}
Lock-free thread-safe Fibonacci number generator
java;fibonacci sequence;lock free
BigInteger operations are slow. Each iteration through the process you are creating a new BigInteger, as well as a new FibonacciNumber instance.These instances are likely more expensive to process (and garbage collect) than the time saved through lock-free management. Still, using a three-state operation you can solve this problem without the FibonacciNumber class:protected final AtomicReference<BigInteger> nextRef = new AtomicReference<>(BigInteger.ONE);protected final AtomicReference<BigInteger> currRef = new AtomicReference<>(BigInteger.ONE);public BigInteger next() {    BigInteger current = null;    do {        // spin loop while someone else is updating the reference.        // updating is indicated by a null value in the reference.        current = currRef.getAndSet(null);    } while (current == null);    BigInteger next = nextRef.get();    nextRef.set(next.add(current));    currRef.set(next);    return current;}Note that the above code puts a waiting process in to a spin lock (100% CPU) instead of locking. This is the same as your code.My preference would be to use a more traditional Lock (or even synchronization) and block threads that are waiting.