Using Hegel to test arithmetics

[pedrolamarao]

Hello all! I have recently added Hegel tests to an arithmetics study project to great effect. You can find the project here: https://github.com/laboratorio-purpura/arithmetics-cxx

Some of the division algorithms impose restrictions on the operands. The nonzero requirement is easy to implement with assume. I am still unsure how best to provide normalized integers.

[Liam-DeVoe]

Hi Pedro - cool to see you using all the hegel libraries, and thanks for your great feedback :)

Can you say more about "normalized integers"? I'm not familiar with that term. In general, using assume or .filter is great for edge cases that are annoying to satisfy constructively, while for anything more complicated you generally want to define a generator that produces valid test cases by construction.

If you share an example of the kind of values you want to generate, I could say more!

[pedrolamarao]

"normalized" means in practice that the most significant bit is set, and is a property of the divisor required by some division algorithms. When generating such a divisor, you may generate any intermediate word, but the topmost word must have the top bit set.

When using the list and integer generator, this is, of course, easy to "fix", something like this:

auto y = tc.draw( vectors<uint64_t>( words<uint64_t>(), { .min_size = 1 } ) );
y[ size(y) - 1 ] |= 1 << 63;

Since Hegel is not being told about the restriction, I wonder if "fixing" like this will negatively impact Hegel's work in any way.

[Liam-DeVoe]

In general, Hegel is quite robust to transformations like this - this will work fine!

However, you can do better. The problem with this generator is half of the generated range [0, 2^64] maps to the same semantic value y in your code. Hegel might generate multiple integers in [2^63, 2^64], thinking it's doing useful work, even though your program treats them the same.

In this case, you can ask Hegel for only the range which can actually vary, and then set the top bit yourself. So ask Hegel for an integer in [0, 2^63], and set the top bit yourself to make it a normalized u64 by construction.

Again, this is a very minor efficiency improvement, and your generator will work fine without doing this!

[pedrolamarao]

Today I experimented writing a composite generator in Go, this is what I came up with. I think this is very reasonable and the tests become very legible.

func hegelNormalLongInteger(minSize, maxSize int) hegel.Generator[[]uint] {
	const Bits = bits.UintSize
	return hegel.Composite[[]uint](func(ht *hegel.TestCase) []uint {
		mid := hegel.Draw[[]uint](ht,
			hegel.Lists(hegel.Integers[uint](0, math.MaxUint)).MinSize(minSize).MaxSize(maxSize-1),
		)
		top := hegel.Draw(ht,
			hegel.Integers[uint](1<<Bits-1, math.MaxUint),
		)
		integer := make([]uint, len(mid)+1)
		copy(integer, mid)
		integer[len(mid)] = top
		return integer
	})
}