Квадратный корень на i8080

[shoorick]

Итерации по Ньютону. Может, кому пригодится

;-----------------------------------------------------------------------
;   HL = SQRT(HL)
;-----------------------------------------------------------------------
sqrt:
;-----------------------------------------------------------------------
    mov  a,h
    ana  l
    inr  a
    jz   .FFFF
;-----------------------------------------------------------------------
    xchg
.loop:
    mov  b,h
    mov  c,l
    push d
    push b
    lxi  h,0
    call gg_d32a
    pop  h
    push h
    dad  d
    mov  a,h
    rar
    mov  h,a
    mov  a,l
    rar
    mov  l,a
;-----------------------------------------------------------------------
    pop  b
    pop  d
    mov  a,b
    cmp  h
    jnz  .loop
    mov  a,l
    cmp  c
    jnz  .loop
;-----------------------------------------------------------------------
    ret 
;-----------------------------------------------------------------------
.FFFF:
    mov h,a
    ret      
;-----------------------------------------------------------------------

Использует подпрограмму деления Д32А из книжки Гуртовцева и Гудыменко

Скрытый текст

;-----------------------------------------------------------------------
;   HLDE / BC = DE (HL)
;   CY=0 -> result overflow
;-----------------------------------------------------------------------
proc gg_d32a ; Д32А
;-----------------------------------------------------------------------
    mov  a,l
    sub  c
    mov  a,h
    sbb  b
    rnc
    call negb
    xra  a
.loop:
    dad  h
    rar
    xchg
    dad  h
    xchg
    jnc  .m1
    inx  h
.m1:
    push h
    dad  b
    jnc  .m2
    ral
.m3:
    inx  d
    inx  sp
    inx  sp
    adi  16
    jnc  .loop
;    stc
    ret
.m2:
    ral
    jc   .m3
    pop  h
    adi  16
    jnc  .loop
;    stc
    ret 
;-----------------------------------------------------------------------
endp    
;-----------------------------------------------------------------------
proc negb
    mov  a,b
    cma
    mov  b,a
    mov  a,c
    cma
    mov  c,a
    inx  b
    ret
endp    
;-----------------------------------------------------------------------

[свернуть]

[Advertiser]

[b2m]

Моё изобретение Столбиком в двоичном виде:

SHFT:	XCHG
	DAD H
	XCHG
	DAD H
	RNC
	INX D
	RET

; вход: HL - квадрат числа
; выход: B - число
; DE - разница между исходным числом и квадратом
SQRT:	LXI B,8
	LXI D,0
SQRT1:	CALL SHFT
	CALL SHFT
	PUSH H
	MOV A,B
	ADD A
	MOV B,A
	CMA
	MOV L,A
	MVI H,0FFh
	DAD H
	INX H
	DAD D
	JNC SQRT2
	INR B
	XCHG
SQRT2:	POP H
        DCR C
	JNZ SQRT1
	RET

Всего 8 итераций!

[shoorick]

работает!
принимаем на вооружение

[shoorick]

А заодно в виде упражнения и кубический 8)

;=======================================================================
;   E = CBRT(HL)
;-----------------------------------------------------------------------
cbrt:
;-----------------------------------------------------------------------
    push h
    lxi  d,16 shl 8 
.loop:
    mov  a,e 
    add  e
    mov  e,a
    mov  h,e 
    inr  h   
    push d
    call umul88 
    pop  d
    push h
    pop  b
    dad  h 
    dad  b 
    inx  h 
    mov  a,d
    dcr  a
    jz   .ok
.shift:
    dad  h
    jc   .skip
    dcr  a
    jnz  .shift
.ok:    
    pop  b
    mov  a,c
    sub  l
    mov  l,a
    mov  a,b
    sbb  h
    jc   .endif
    mov  b,a
    mov  c,l
    inr  e
.endif:
    push b
.skip:
    mov  a,d
    sui  3
    mov  d,a
    jp   .loop            
    pop  b
    ret      
;=======================================================================

использует умножение из той же книжки

Скрытый текст

;-----------------------------------------------------------------------
;   HL = H * E
;   BС,E:CONST
;-----------------------------------------------------------------------
umul88 equ gg_u88b1
;-----------------------------------------------------------------------
proc gg_u88b1 ; У88Б1 модифицированная
;-----------------------------------------------------------------------
    mvi  d,0
    mvi  l,0
    mvi  a,8
.loop:
    dad  h
    jnc  .skip
    dad  d
.skip:
    dcr  a
    jnz  .loop
	ret
;-----------------------------------------------------------------------
endp

[свернуть]

без него не смог, так как портировал данный код из другой известной книжки:

Скрытый текст

int icbrt(unsigned x){
  int s;
  unsigned y,b;
  s=15;
  y=0;
  while (s>=0) {
    y = 2*y;
    b = (3*y*(y+1)+1)<<s;
    //b = b & 0xFFFF;
    if (x>=b) {
      x = x - b;
      y = y + 1;
    }
    s = s - 3;
    //printf("x=%6u, y=%6u, b=%6u, s=%2i\n",x,y,b,s);
  }
  return y;
}

[свернуть]

[b2m]

портировал данный код из другой известной книжки

По структуре очень похож на то, что я сделал выше для квадратного. Наверное, несложно будет модифицировать моё творение, чтобы оно кубический корень извлекало.

Вот моё в таком-же виде:

int isqrt(unsigned x){
  int s;
  unsigned y,b;
  s=14;
  y=0;
  while (s>=0) {
    y = 2*y;
    b = (2*y+1)<<s;
    if (x>=b) {
      x = x - b;
      y = y + 1;
    }
    s = s - 2;
  }
  return y;
}

- - - Добавлено - - -

Только вот вычислять 3*y*(y+1)+1 вместо 2*y+1 чуточку сложнее

- - - Добавлено - - -

Интересно, а можно вывести формулу для b = ???, чтобы оно например корень 5-й степени извлекало?

- - - Добавлено - - -

2*y+1 = (y+1)^2 - y^2
3*y*(y+1)+1 = 3*y^2 + 3*y + 1 = (y+1)^3 - y^3
Что у нас там для пятой степени получается?

- - - Добавлено - - -

(y+1)^5 - y^5 = 5*y^4 + 10*y^3 + 10*y^2 + 5*y + 1 = 5*y*(y*(y*(y+2)+2)+1)+1
Щас проверим

- - - Добавлено - - -

Ха, работает

int isqrt5(unsigned x){
  int s;
  unsigned y,b;
  s=20;
  y=0;
  while (s>=0) {
    y = 2*y;
    b = (5*y*(y*(y*(y+2)+2)+1)+1)<<s;
    if (x>=b) {
      x = x - b;
      y = y + 1;
    }
    s = s - 5;
  }
  return y;
}

Разрядность для тестов увеличил.

[shoorick]

да, не попалась мне такая sqrt...
в хакер-делайт была такая:

int isqrt(unsigned x) {
  unsigned m,y,b;
  m=0x40000000;
  y = 0;
  while (m!=0) {
    b = y | m;
    y = y >> 1;
    if (x>=b) {
      x = x - b;
      y = y | m;
    }
    m = m >> 2;
  }
  return y;

}

-- ввела меня немного в ступор

а с разрядностью - да, попотел, пока понял, что при значениях > 37^3 переполнялось b, победил при помощи "jc .skip"
надо будет попробовать 32-битные процедуры замутить как минимум sqrt

[b2m]

ввела меня немного в ступор

Да, правильность не очевидна И что, работает?

- - - Добавлено - - -

Хотя да, практически то-же самое. Только сдвиги в другую сторону.

[shoorick]

да, работает

[iceoflame]

Напоминает шутку:

ya_frosia: Связка ломов, как правило, тонет
alexei: ya_frosia: Но в ртути прекрасно плавает
zoogenic: alexei: Но если ломы урановые, то и во ртути тонут
alexei: zoogenic: сам топи урановые ломы в ртути

https://lurkmore.co/%D3%F0%E0%ED%EE%...5_%EB%EE%EC%FB

[shoorick]

в вопросе материала для ломов главное помнить о кейворине!