Polynomial interpolation

I've benchmarked FFT/non-FFT based approaches for almost everything in that scale for the last ten years and gotten quite different results.

Build a table left[j] of product-of-ratios for i < j, and another right[k] for i > k, each in linear-time, and combine the two to find the product-of-ratio for i != m in linear time as well.

That's a bit difficult, as most of my work is proprietary, under NDA or aerospace.

Here's an excerpt from a C control panel menu processor, just to show how far I go. One line of active code vs. 21 lines of comments. This was written 16 years ago. I can get back into this codebase almost instantly because of the documentation. More importantly, code reuse is also very easy for the same reason.

    case BUTTON_ENTER:
        // ENTER button clicked
        // 
        // This has the effect of calling the "DURING" handler for the currently selected
        // menu.
        // 
        // ***NOTE***
        // It is the responsibility of the ON_ENTRY handler to decide whether or not
        // to capture the message loop by asserting "state_handler_wants_priority"
        // 
        // Once done with the message loop "state_handler_wants_priority" should be cleared,
        // typically in the ON_EXIT routine
        // 
        // It is up to the handler to do something (or not) with messages.
        // 
        // Parent menus do not generally do much because they are navigation
        // stopping points and their messages are fully handled by the menu_processor() parser.
        //
        // Child menus that are not parents and, therefore, perform a function, 
        // might want to do some work before the menu_processor() parser by capturing messages
        // before they are delivered to the menu_processor() parser.
        //
        dispatch_handler(current_state, DURING);
        break;

    // COMMAND TABLE ----------------------------------------------------------------------------------
    // Use the following template for assignment of SDRAM commands from this table: 
    //
    // {SDRAM_CSn, SDRAM_RASn, SDRAM_CASn, SDRAM_WRn} <= COMMAND_NOP; // Issue command 
    //
    //                            CSn   RASn  CASn  WRn
    //                             |     |     |     |
    parameter COMMAND_NOP    = {1'b0, 1'b1, 1'b1, 1'b1};
    parameter COMMAND_ACT    = {1'b0, 1'b0, 1'b1, 1'b1};
    parameter COMMAND_RD     = {1'b0, 1'b1, 1'b0, 1'b1};
    parameter COMMAND_WR     = {1'b0, 1'b1, 1'b0, 1'b0};
    parameter COMMAND_BST    = {1'b0, 1'b1, 1'b1, 1'b0};
    parameter COMMAND_PRE    = {1'b0, 1'b0, 1'b1, 1'b0};
    parameter COMMAND_REF    = {1'b0, 1'b0, 1'b0, 1'b1};
    parameter COMMAND_LMR    = {1'b0, 1'b0, 1'b0, 1'b0};
    parameter COMMAND_IOEN   = {1'b0, 1'b0, 1'b0, 1'b0};
    parameter COMMAND_IODIS  = {1'b0, 1'b0, 1'b0, 1'b0};
    
    parameter MODE_REGISTER_DEFAULT = 14'b000000_0_011_0_111;    // CAS length = 3
    //                                      |       |  |  |
    //                                      |       |  |  Burst length: 000 = 1; 001 = 2; 010 = 4; 011 = 8; 111 = Full page
    //                                      |       |  |
    //                                      |       |  Burst type: 0 = Sequential; 1 = Interleaved
    //                                      |       |
    //                                      |       CAS Latency: 010 = 2; 011 = 3;
    //                                      |
    //                                      Write mode: 000000 = Burst read and burst write.
    //                                                  000010 = Burst read and single write.

Even if your data isn’t noisy and the point added lies exactly on the previous polynomial (making the problem degenerate) chances are float rounding and numerical stability of your code can have that effect (https://arachnoid.com/polysolve/#x_limits)