ref/include/comb.c
// Note not const. Stomps on source
// Leaves source with invalid z-values, but if they are all set to one, it will
// be correct again. Shrinks combs down to affine with a single inversion. Also
// narrows and reduces to 10 limbs.
Note not const. Stomps on source
Leaves source with invalid z-values, but if they are all set to one, it will
be correct again. Shrinks combs down to affine with a single inversion. Also
narrows and reduces to 10 limbs.
Note not const . Stomps on source Leaves source with invalid z - values but if they are all set to one it will be correct again . Shrinks combs down to affine with a single inversion . Also narrows and reduces to 10 limbs .
void reduce_comb_set(sabs_comb_set_t *result, sabs_comb_set_narrow_t *source) {
  residue_narrow_t z_left;
  residue_narrow_t z_right;
  residue_narrow_t z_inv;
  copy_narrow(&z_left, &source->combs[0].table[0].z);
  for (int i = 1; i < COMB_TABLE_SIZE * COMB_COUNT; ++i) {
    mul_narrow(&source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].x,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].x,
             &z_left);
    mul_narrow(&source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].y,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].y,
             &z_left);
    mul_narrow(&z_left, &z_left,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].z);
  }
  copy_narrow(&z_right,
      &source->combs[COMB_COUNT - 1].table[COMB_TABLE_SIZE - 1].z);
  for (int i = COMB_TABLE_SIZE * COMB_COUNT - 2; i >= 0; --i) {
    mul_narrow(&source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].x,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].x,
             &z_right);
    mul_narrow(&source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].y,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].y,
             &z_right);
    mul_narrow(&z_right, &z_right,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].z);
  }
  invert_narrow(&z_inv, &z_right);
  for (int i = 0; i < COMB_TABLE_SIZE * COMB_COUNT; ++i) {
    residue_narrow_t xy;
    mul_narrow(&source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].x,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].x,
             &z_inv);
    copy_narrow(&result->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].x,
           &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].x);
    mul_narrow(&source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].y,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].y,
             &z_inv);
    copy_narrow(&result->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].y,
           &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].y);
    mul_narrow(&xy,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].x,
             &source->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].y);
    mul_narrow_const(&xy, &xy, D);
    copy_narrow(
      &result->combs[i / COMB_TABLE_SIZE].table[i % COMB_TABLE_SIZE].dt,
      &xy);
  }
}
void reduce_comb_set ( sabs_comb_set_t * result , sabs_comb_set_narrow_t * source ) { residue_narrow_t z_left ; residue_narrow_t z_right ; residue_narrow_t z_inv ; copy_narrow ( & z_left , & source -> combs [ 0 ] . table [ 0 ] . z ) ; for ( int i = 1 ; i < COMB_TABLE_SIZE * COMB_COUNT ; ++ i ) { mul_narrow ( & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . x , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . x , & z_left ) ; mul_narrow ( & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . y , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . y , & z_left ) ; mul_narrow ( & z_left , & z_left , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . z ) ; } copy_narrow ( & z_right , & source -> combs [ COMB_COUNT - 1 ] . table [ COMB_TABLE_SIZE - 1 ] . z ) ; for ( int i = COMB_TABLE_SIZE * COMB_COUNT - 2 ; i >= 0 ; -- i ) { mul_narrow ( & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . x , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . x , & z_right ) ; mul_narrow ( & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . y , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . y , & z_right ) ; mul_narrow ( & z_right , & z_right , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . z ) ; } invert_narrow ( & z_inv , & z_right ) ; for ( int i = 0 ; i < COMB_TABLE_SIZE * COMB_COUNT ; ++ i ) { residue_narrow_t xy ; mul_narrow ( & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . x , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . x , & z_inv ) ; copy_narrow ( & result -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . x , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . x ) ; mul_narrow ( & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . y , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . y , & z_inv ) ; copy_narrow ( & result -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . y , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . y ) ; mul_narrow ( & xy , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . x , & source -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . y ) ; mul_narrow_const ( & xy , & xy , D ) ; copy_narrow ( & result -> combs [ i / COMB_TABLE_SIZE ] . table [ i % COMB_TABLE_SIZE ] . dt , & xy ) ; } }
Note not const.
Note not const .
// This is an interview question that is actually applicable. For every entry // in the table we want to multiply it by every z entry but its own. We // do it in two passes, accumulating z values as we go from left to right and // right to left. // Now that all the entries have common denominators, perform a single // inversion // Divide by the common z and narrow. // The combs store DT rather than T for faster additions.