Tuesday, 27 May 2014

GSoC :- Week 1

My proposal "Implementing the LLL algorithm in FLINT" has been accepted for Google Summer of Code 2014. The official coding period began last week (May 19) and so I have started to code. The source code can be found here.

What did you work on this week?

Implemented the _fmpz_vec_dot function in fmpz_vec module for use in fmpz_lll_heuristic_dot.

- Implemented the fmpz_lll_heuristic_dot function for use in fmpz_lll_check_babai_heuristic_d.

- Implemented the _fmpz_vec_get_d_vec_2exp function in fmpz_vec module for use in fmpz_lll_check_babai.

- Wrote the fmpz_lll_check_babai function.

- Wrote the fmpz_lll_check_babai_heuristic_d function.

- Made changes to d_mat, d_vec modules and fmpq_mat implementation of classical LLL based on mentor comments.

What do you plan on doing next week?

- Change fmpz_lll_heuristic_dot to use the new _d_vec_dot heurstic function and test it.

- Document the Babai functions.

- Write the fmpz_lll_d function.

- Test, profile and document fmpz_lll_d.

- Increase the pace, maybe? :)

Are you stuck on anything?

I am not stuck because of these issues, but would certainly appreciate comments to improve the  code.

- How to check if a double is NaN?: IEEE standard specifies f != f will be true only if f is NaN and so, I use this as the check. However, compilers may optimize this out. This requires checking with different compilers. The condition cannot be changed to use isnan function in math.h as that was introduced in C99.

- Will +-0 cause a problem? -0.0 == 0.0 returns true, so it seems to be okay.

- Hackish way of finding ulps in _d_vec_dot_heurstic. Is there a better way not using functions like nextafter which is since C99?

- y = rint(x); is not ANSI C. I used if(x < 0) y = ceil(x-0.5); else y = floor(x+0.5); instead. Here's the output on my machine with the rounding mode as default.
rint(5.5) = 6.0 rint(-1.5) = -2.0
ceil(5.5-0.5) = 5.0 floor(5.5+0.5) = 6.0 ceil(-1.5-0.5) = -2.0 floor(-1.5+0.5) = -1.0