Faktoryzacja przez dzielenie przez sume cyfr, implementacja

Faktoryzację polegającą na sprawdzaniu reszt z dzielenia przez kolejne liczby można zaimplementować mniej standardowo, sprawdzanych przypadków jest więcej, lecz złożoność arytmetyczna się polepsza.
Teoria jest taka, jak opisana w sąsiednim poście, kiedy szukałem ciągu konwersji wskazującego dzielnik.
Liczbę n przedstawiam w systemie o podstawie 2^i, oraz mając te m cyfr sprawdzam cechami podzielności przez liczby 2^i-k, k nieparzyste malejące od 2^i-1 do 1. Jeśli uzyskana suma cyfr dzieli / jest wielokrotnością podstawy, mamy dzielnik.

Algorytm wykorzystuje konwersję podwajającą podstawę. Oto jej implementacja.
Liczba dana jest tablicą unsigned int a[8], w której cyfra najmniej znacząca jest ostatnim elementem tablicy. Podstawą systemu jest unsigned int p.
[\code=cpp]
void divp( unsigned int * a, unsigned int p ) {
  unsigned int k=0x80; // 2^i
  unsigned int i=0; // iterator tablicy cyfr a
  unsigned int b=0; // zmienna pomocnicza
  while(i++<length) { // tu length = 8, tablica 8
    b = b*p + a[i];
    a[i] = b/k; // cyfra to czesc calkowita
    b %= k; // reszta przenoszona dalej
    k /= 2; // nastepny bit
  }
}
[\code]

Sam rozkład zaczyna się przedstawienia liczby w systemie szesnastkowej. Następuje sprawdzenie cech podzielności przez 2, 3, 5 (suma cyfr jest podzielna przez te wartości). Dalej podział na przedziały binarne, zaś w każdym z nich dla kolejnych wartości nieparzystych wykorzystywana cecha podzielności przez p.
[\code=cpp]
int rozklad() {
  unsigned int a[] = ; // inicjowanie
  unsigned int s = ; // suma dla inicjacji
  if(s) ; // sprawdzenie malych dzielnikow
  unsigned int p=9; // zaczynamy od systemu siodemkowego 16-9
  unsigned int k=7; // 16-9 = 7, do cechy podzielnosci
  while(1) {
    unsigned int i= a.length()-1; // na cyfrę najmniej znaczącą
    s = a[i]; // sumowanie, inicjacja
    unsigned int t=1; // zmienna wspomagająca znajdowanie wspolczynnikow
    while(--i) {
      t = (k*t)%p; // dla cyfry lub aktualnej lub wspolczynnika przy i-1
      s = s + (a[i]*t)%p; // aktualna cyfra
    }
    if( p==s ) return p; // dzielnikiem jest p
    if( 2>k ) {
      k=p; // przeliczenie postaci liczby a[]
      divp(a, k+1); // zmienia dlugosc a
    } else k -= 2; // do następnego dzielenia
    p += 2; // następna podstawa
    if() ;// wyjscie w przypadku liczby pierwszej
  }
}
[\code]

Złożoność modułu divp jest liniowa względem długości cyfr liczby n, czyli logarytmiczna. Pętla faktoryzacji rozdziela przypadki na przedziały [2^i, 2^(i+1)), których jest logarytm z n.
W każdym takim przedziale następuje sumowanie cyfr liczby modulo p, znowu mające krotność logarytmu z n. Pętla ma dokładnie 2^(i-1) przejść, zakończonych uruchomieniem funkcji divp() (liniowe, gdyż 2^(2i)<n<2^(2i+2)).
Najwięcej kosztują przypadki dla dużych k (ale wtedy a jest stosunkowo 'krótka'). Ogólnie złożoność pesymistyczna jest O(n ln n).
Z kolei iloczyny cząstkowe wykonywane modulo nie mają wartości większych niż potęga 2 przekraczająca n.
Jeden z czynników występujących iloczynów ma wykres piłokształtny (liniowo malejący o 2, gwałtowny wzrost do 2^i po osiągnięciu takiej podstawy).