Advent of PBT 2021 - Day 7 - Solution
Tags: challenge, testing, webdev, javascript
Published: 2021-12-07 07:28:39

---
title: Advent of PBT 2021 - Day 7 - Solution
published: true
description: Advent of Property Based Testing 2021 - Day 7 - Solution
tags: challenge,testing,webdev,javascript
//cover_image: https://direct_url_to_image.jpg
---

Our algorithm was: **fibonacci**.
[Go to the subject itself for more details](https://dev.to/dubzzz/advent-of-pbt-2021-day-7-2e89)

CodeSandbox with a possible set of properties you may have come with: https://codesandbox.io/s/advent-of-pbt-day-7-solution-ts0nw?file=/src/index.spec.ts&previewwindow=tests

---

Fibonacci a function coming from mathematics, it comes with lots of properties out of the box. We can just enumerate some of them to confirm our code works fine.

As our implementation of `fibonacci` comes with a linear time-complexity we will cap the maximal value we pass to it to `MaxN = 1000`.

---

## Property 1: should be equal to the sum of fibo(n-1) and fibo(n-2)

Written with fast-check:

```ts
it("should be equal to the sum of fibo(n-1) and fibo(n-2)", () => {
  fc.assert(
    fc.property(fc.integer({ min: 2, max: MaxN }), (n) => {
      expect(fibonacci(n)).toBe(fibonacci(n - 1) + fibonacci(n - 2));
    })
  );
});
```

## Property 2: should fulfill fibo(p)*fibo(q+1)+fibo(p-1)*fibo(q) = fibo(p+q)

Written with fast-check:

```ts
it("should fulfill fibo(p)*fibo(q+1)+fibo(p-1)*fibo(q) = fibo(p+q)", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 1, max: MaxN }),
      fc.integer({ min: 0, max: MaxN }),
      (p, q) => {
        expect(fibonacci(p + q)).toBe(
          fibonacci(p) * fibonacci(q + 1) + fibonacci(p - 1) * fibonacci(q)
        );
      }
    )
  );
});
```

## Property 3: should fulfill fibo(2p-1) = fibo²(p-1)+fibo²(p)

Written with fast-check:

```ts
it("should fulfill fibo(2p-1) = fibo²(p-1)+fibo²(p)", () => {
  // Special case of the property above
  fc.assert(
    fc.property(fc.integer({ min: 1, max: MaxN }), (p) => {
      expect(fibonacci(2 * p - 1)).toBe(
        fibonacci(p - 1) * fibonacci(p - 1) + fibonacci(p) * fibonacci(p)
      );
    })
  );
});
```

## Property 4: should fulfill Catalan identity

Written with fast-check:

```ts
it("should fulfill Catalan identity", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 0, max: MaxN }),
      fc.integer({ min: 0, max: MaxN }),
      (a, b) => {
        const [p, q] = a < b ? [b, a] : [a, b];
        const sign = (p - q) % 2 === 0 ? 1n : -1n; // (-1)^(p-q)
        expect(
          fibonacci(p) * fibonacci(p) - fibonacci(p - q) * fibonacci(p + q)
        ).toBe(sign * fibonacci(q) * fibonacci(q));
      }
    )
  );
});
```

## Property 5: should fulfill Cassini identity

Written with fast-check:

```ts
it("should fulfill Cassini identity", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 1, max: MaxN }),
      fc.integer({ min: 0, max: MaxN }),
      (p) => {
        const sign = p % 2 === 0 ? 1n : -1n; // (-1)^p
        expect(
          fibonacci(p + 1) * fibonacci(p - 1) - fibonacci(p) * fibonacci(p)
        ).toBe(sign);
      }
    )
  );
});
```

## Property 6: should fibo(nk) divisible by fibo(n)

Written with fast-check:

```ts
it("should fibo(nk) divisible by fibo(n)", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 1, max: MaxN }),
      fc.integer({ min: 0, max: 100 }),
      (n, k) => {
        expect(fibonacci(n * k) % fibonacci(n)).toBe(0n);
      }
    )
  );
});
```

## Property 7: should fulfill gcd(fibo(a), fibo(b)) = fibo(gcd(a,b))

Written with fast-check:

```ts
it("should fulfill gcd(fibo(a), fibo(b)) = fibo(gcd(a,b))", () => {
  fc.assert(
    fc.property(
      fc.integer({ min: 1, max: MaxN }),
      fc.integer({ min: 1, max: MaxN }),
      (a, b) => {
        const gcdAB = Number(gcd(BigInt(a), BigInt(b)));
        expect(gcd(fibonacci(a), fibonacci(b))).toBe(fibonacci(gcdAB));
      }
    )
  );
});
```

This property needs a helper function called `gcd` that could be written as follow:

```ts
function gcd(_a: bigint, _b: bigint): bigint {
  let a = _a < 0n ? -_a : _a;
  let b = _b < 0n ? -_b : _b;
  if (b > a) {
    const temp = a;
    a = b;
    b = temp;
  }
  while (true) {
    if (b === 0n) return a;
    a = a % b;
    if (a === 0n) return b;
    b = b % a;
  }
}
```

---

[Back to "Advent of PBT 2021"](https://dev.to/dubzzz/advent-of-pbt-2021-13ee) to see topics covered during the other days and their solutions.

More about this serie on [@ndubien](https://twitter.com/ndubien) or with the hashtag [#AdventOfPBT](https://twitter.com/search?q=%23AdventOfPBT).