On Fri, 29 Jul 2005, Michal Schmidt wrote:

Rafael J. Wysocki wrote:

quoted

On Friday, 29 of July 2005 21:46, Michal Schmidt wrote:

quoted

The function calc_nr uses an iterative algorithm to calculate the number 
of pages needed for the image and the pagedir. Exactly the same result 
can be obtained with a one-line expression.

Could you please post the proof?

Rafael

OK, attached is a proof-by-brute-force program. It compares the results 
of the original function and the simplified one.

Here's a more general proof.

As I understand it, calc_nr is given nr_copy, the number of data pages
that need to be written out, and it has to return the number of pages
needed to hold the image data plus a bunch of PBE pagedir indexes, where
each page gets one index (and pages containing PBEs need their own indexes
as well).

For brevity, let n = nr_copy, let p = PBES_PER_PAGE, and let x be the 
number of pagdir pages needed.  Since each page can hold p PBEs, there 
will be room to store px PBEs.  The total number of pages is n + x, so 
the routine needs to find the smallest value of x for which

	px >= n + x

or

	(p-1)x >= n

or

	x >= n / (p-1).

The obvious solution is

	x = ceiling(n / (p-1)),

so calc_nr should return n + ceiling(n / (p-1)), which is exactly what 
Michal's patch computes.

Alan Stern