`On Saturday, 30 of July 2005 03:35, Alan Stern wrote:> On Fri, 29 Jul 2005, Michal Schmidt wrote:> > > Rafael J. Wysocki wrote:> > > On Friday, 29 of July 2005 21:46, Michal Schmidt wrote:> > > > > >>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.Nice. :-)Could we perhaps add your proof to the Michal's patch as a comment,for reference?Rafael-- - Would you tell me, please, which way I ought to go from here?- That depends a good deal on where you want to get to.		-- Lewis Carroll "Alice's Adventures in Wonderland"-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`