The Fibonacci Calculator

The holiday season is all about traditions, and the annual holiday puzzle has become a tradition here at OneSpin. Two years ago, we challenged engineers everywhere to solve the famous Einstein’s Riddle using a formal tool. We received some interesting solutions. Last year, we drew an even bigger response to our invitation to tackle the “World’s Hardest Sudoku.” These puzzles are fun, of course, but the different approaches taken by those submitting solutions also reveal a lot about the power and flexibility of assertions and formal verification.

This year, we invite everyone to consider the Fibonacci numbers, which make up the Fibonacci sequence. You probably remember this from a math class years ago: the sequence starts with 0 and 1, and then each new Fibonacci number is the sum of the previous two numbers:

Fibonacci numbers are important in numerous branches of mathematics, but I was drawn to this series as a topic for this year’s puzzle mostly because it occurs in many places in the natural world. Commonly cited examples include the pattern of branches on some trees, the pattern of leaves on stems, and the arrangement of leaves or fruit on certain plants. With some idealized assumptions, generations of honeybees and rabbits may also follow the Fibonacci series.

While the concept of Fibonacci numbers had been known centuries earlier in India, they are named after an Italian mathematician also known as Leonardo of Pisa. In the early thirteenth century, he published books that included discussions of the series that now bears his name as well as calculation of interest and our current system of numerals with place values. He was a contemporary of Campanus of Novara, who translated Euclid’s “Elements” into Latin, the first printed edition of this seminal work.

This holiday season, we ask engineers to design a digital circuit that calculates Fibonacci numbers. We have prepared a sample solution for you, but we know that it could be improved. Digital design would be easy without targets on power, performance and area. Your solution should not only be correct, but also fast and simple. Can you reduce the number of branches in your code, use fewer gates, and identify redundant flops, while also improving performances of a given benchmark? Besides the sample solution, we provide a set of SystemVerilog assertions that your solution must satisfy, a benchmark in the form of cover properties to measure cycle-based performances, and a formula to compute the design complexity score.

If you are up for the challenge, please visit onespin.com/holidaypuzzle to get all the details and submit your solution. We have several exciting prizes up for grabs, including one for the solution with the best score, which will be determined automatically using a OneSpin script, and one for the most voted solution. I will share the winners and their approaches in a follow-up blog early next year.

Deadline for participation is midnight (CET) Sunday, January 13, 2019.

I wish you the best of luck, and a great holiday season!