PureBasic - форум

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » PureBasic - форум » OpenSource » Работа с длинными числами


Работа с длинными числами

Сообщений 1 страница 9 из 9

1

Код:
Procedure.s DetermineSign(a.s, b.s, operation.s)
    Protected signA = 1
    Protected signB = 1
    
    ; Определяем знаки чисел
    If Left(a, 1) = "-"
        signA = -1
        a = Right(a, Len(a) - 1)
    EndIf
    If Left(b, 1) = "-"
        signB = -1
        b = Right(b, Len(b) - 1)
    EndIf
    
    ; Определяем знак результата в зависимости от операции
    Select operation
        Case "+"
            If signA = signB
                ProcedureReturn Str(signA)
            Else
                If signA = 1
                    ProcedureReturn "subtract"
                Else
                    ProcedureReturn "subtract_reverse"
                EndIf
            EndIf
        Case "-"
            If signA = signB
                If signA = 1
                    ProcedureReturn "subtract"
                Else
                    ProcedureReturn "subtract_reverse"
                EndIf
            Else
                ProcedureReturn Str(signA)
            EndIf
        Case "*"
            ProcedureReturn Str(signA * signB)
        Case "/"
            ProcedureReturn Str(signA * signB)
    EndSelect
  EndProcedure
  
Procedure.s String(char.s, count)
    Protected result.s = ""
    For i = 1 To count
        result + char
    Next
    ProcedureReturn result
EndProcedure

Declare.s AddLongNumbers(a.s,b.s)

Procedure.s SubtractLongNumbers(a.s, b.s)
    Protected signResult.s = DetermineSign(a, b, "-")
    
    ; Убираем знаки из чисел
    If Left(a, 1) = "-"
        a = Right(a, Len(a) - 1)
    EndIf
    If Left(b, 1) = "-"
        b = Right(b, Len(b) - 1)
    EndIf
    
    ; Если знак результата требует сложения
    If signResult = "1" Or signResult = "-1"
        ProcedureReturn AddLongNumbers(a, b)
    EndIf
    
    ; Выполняем вычитание
    Protected borrow = 0
    Protected result.s = ""
    Protected i, diff, digitA, digitB
    
    ; Выравниваем числа по десятичной точке
    Protected aPoint = FindString(a, ".", 1)
    Protected bPoint = FindString(b, ".", 1)
    
    If aPoint = 0
        a + ".0"
        aPoint = Len(a) - 1
    EndIf
    If bPoint = 0
        b + ".0"
        bPoint = Len(b) - 1
    EndIf
    
    ; Выравниваем дробные части
    While Len(a) - aPoint < Len(b) - bPoint
        a + "0"
    Wend
    While Len(b) - bPoint < Len(a) - aPoint
        b + "0"
    Wend
    
    ; Выравниваем целые части
    While aPoint < bPoint
        a = "0" + a
        aPoint + 1
    Wend
    While bPoint < aPoint
        b = "0" + b
        bPoint + 1
    Wend
    
    ; Вычитаем цифры справа налево
    For i = Len(a) To 1 Step -1
        If Mid(a, i, 1) = "."
            result = "." + result
            Continue
        EndIf
        
        digitA = Val(Mid(a, i, 1)) - borrow
        digitB = Val(Mid(b, i, 1))
        
        If digitA < digitB
            digitA + 10
            borrow = 1
        Else
            borrow = 0
        EndIf
        
        diff = digitA - digitB
        result = Str(diff) + result
    Next
    
    ; Убираем ведущие нули
    While Left(result, 1) = "0" And Len(result) > 1 And Mid(result, 2, 1) <> "."
        result = Right(result, Len(result) - 1)
    Wend
    
    ; Добавляем знак результата
    If signResult = "-1"
        result = "-" + result
    EndIf
    
    ProcedureReturn result
EndProcedure

Procedure.s AddLongNumbers(a.s, b.s)
    Protected signResult.s = DetermineSign(a, b, "+")
    
    ; Убираем знаки из чисел
    If Left(a, 1) = "-"
        a = Right(a, Len(a) - 1)
    EndIf
    If Left(b, 1) = "-"
        b = Right(b, Len(b) - 1)
    EndIf
    
    ; Если знак результата требует вычитания
    If signResult = "subtract"
        ProcedureReturn SubtractLongNumbers(a, b)
    ElseIf signResult = "subtract_reverse"
        ProcedureReturn SubtractLongNumbers(b, a)
    EndIf
    
    ; Выполняем сложение
    Protected carry = 0
    Protected result.s = ""
    Protected i, j, sum, digitA, digitB
    
    ; Выравниваем числа по десятичной точке
    Protected aPoint = FindString(a, ".", 1)
    Protected bPoint = FindString(b, ".", 1)
    
    If aPoint = 0
        a + ".0"
        aPoint = Len(a) - 1
    EndIf
    If bPoint = 0
        b + ".0"
        bPoint = Len(b) - 1
    EndIf
    
    ; Выравниваем дробные части
    While Len(a) - aPoint < Len(b) - bPoint
        a + "0"
    Wend
    While Len(b) - bPoint < Len(a) - aPoint
        b + "0"
    Wend
    
    ; Выравниваем целые части
    While aPoint < bPoint
        a = "0" + a
        aPoint + 1
    Wend
    While bPoint < aPoint
        b = "0" + b
        bPoint + 1
    Wend
    
    ; Складываем цифры справа налево
    For i = Len(a) To 1 Step -1
        If Mid(a, i, 1) = "."
            result = "." + result
            Continue
        EndIf
        
        digitA = Val(Mid(a, i, 1))
        digitB = Val(Mid(b, i, 1))
        
        sum = digitA + digitB + carry
        carry = sum / 10
        result = Str(sum % 10) + result
    Next
    
    If carry > 0
        result = Str(carry) + result
    EndIf
    
    ; Добавляем знак результата
    If signResult = "-1"
        result = "-" + result
    EndIf
    
    ProcedureReturn result
EndProcedure
  

Procedure.s MultiplyLongNumbers(a.s, b.s)
    Protected signResult.s = DetermineSign(a, b, "*")
    
    ; Убираем знаки из чисел
    If Left(a, 1) = "-"
        a = Right(a, Len(a) - 1)
    EndIf
    If Left(b, 1) = "-"
        b = Right(b, Len(b) - 1)
    EndIf
    
    ; Убираем десятичные точки и запоминаем количество знаков после точки
    Protected aPoint = FindString(a, ".", 1)
    Protected bPoint = FindString(b, ".", 1)
    
    If aPoint > 0
        a = RemoveString(a, ".")
        aDecimalPlaces = Len(a) - aPoint + 1
    Else
        aDecimalPlaces = 0
    EndIf
    
    If bPoint > 0
        b = RemoveString(b, ".")
        bDecimalPlaces = Len(b) - bPoint + 1
    Else
        bDecimalPlaces = 0
    EndIf
    
    ; Умножаем числа как целые
    Protected result.s = "0"
    Protected i, j, carry, product
    Protected temp.s
    
    For i = Len(b) To 1 Step -1
        carry = 0
        temp = ""
        
        For j = Len(a) To 1 Step -1
            product = Val(Mid(a, j, 1)) * Val(Mid(b, i, 1)) + carry
            carry = product / 10
            temp = Str(product % 10) + temp
        Next
        
        If carry > 0
            temp = Str(carry) + temp
        EndIf
        
        ; Сдвигаем результат влево на соответствующее количество разрядов
        temp + String("0", Len(b) - i)
        result = AddLongNumbers(result, temp)
    Next
    
    ; Вставляем десятичную точку
    Protected totalDecimalPlaces = aDecimalPlaces + bDecimalPlaces
    If totalDecimalPlaces > 0
        ; Если количество десятичных разрядов больше длины результата, добавляем ведущие нули
        If totalDecimalPlaces > Len(result)
            result = String("0", totalDecimalPlaces - Len(result)) + result
        EndIf
        ; Вставляем точку
        result = Left(result, Len(result) - totalDecimalPlaces) + "." + Right(result, totalDecimalPlaces)
    EndIf
    
    ; Убираем ведущие нули
    While Left(result, 1) = "0" And Len(result) > 1 And Mid(result, 2, 1) <> "."
        result = Right(result, Len(result) - 1)
    Wend
    
    ; Убираем лишние нули после точки
    If FindString(result, ".", 1) > 0
        While Right(result, 1) = "0"
            result = Left(result, Len(result) - 1)
        Wend
        If Right(result, 1) = "."
            result = Left(result, Len(result) - 1)
        EndIf
    EndIf
    
    ; Добавляем знак результата
    If signResult = "-1"
        result = "-" + result
    EndIf
    
    ProcedureReturn result
  EndProcedure
  
a.s = "123.456"
b.s = "78.98765"
  
Debug "Произведение: " + MultiplyLongNumbers(a, b)
Debug ValD(a)*ValD(b)

Чё-то я где-то тут не допираю - умножает нормально но точка в числе стоит не там, как исправить?

0

2

Пока не знаю ответ, но глядя на код возникает желание оптимизировать, например:

Код:
While Left(result, 1) = "0"

здесь строковые функции можно заменить на

Код:
While Asc(result) = '0'

У меня тоже было желание написать код умножения, как мы делали в школе считая числа строковыми данными, тем самым избавиться от ограничения длинны вычислений.
Если что есть библиотека BigInt

0

3

AZJIO, судя по названию bigINT INTEGER - это же целые числа, а мне надо с плавающей запятой.
Вот кусок присоединия точки в число, в нём что-то не так

Код:
 ; Вставляем точку
        result = Left(result, Len(result) - totalDecimalPlaces) + "." + Right(result, totalDecimalPlaces)

0

4

1. упрощение кода:

Код:
If aPoint > 0

заменить на

Код:
If aPoint

2. упрощение кода:

Код:
If Left(a, 1) = "-"

заменить на

Код:
If Asc(a) = '-'

3. упрощение кода:

Код:
    ; Убираем ведущие нули
    While Left(result, 1) = "0" And Len(result) > 1 And Mid(result, 2, 1) <> "."
        result = Right(result, Len(result) - 1)
    Wendd

мой вариант

Код:
tmp$ = "0000001"
tmp$ = LTrim(tmp$, "0")
If Asc(tmp$) = 0 Or Asc(tmp$) = '.'
	tmp$ = "0" + tmp$
EndIf
Debug tmp$

4. упрощение кода:

Код:
; Убираем лишние нули после точки
If FindString(result, ".", 1) > 0
	While Right(result, 1) = "0"
    result = Left(result, Len(result) - 1)
	Wend
	If Right(result, 1) = "."
    result = Left(result, Len(result) - 1)
	EndIf
EndIf

мой вариант

Код:
; Убираем лишние нули после точки
If FindString(result, ".")
	result = RTrim(result, "0")
	result = RTrim(result, ".")
EndIf

5. упрощение кода:

Код:
    ; Определяем знаки чисел
    If Left(a, 1) = "-"
        signA = -1
        a = Right(a, Len(a) - 1)
    EndIf
    If Left(b, 1) = "-"
        signB = -1
        b = Right(b, Len(b) - 1)
    EndIf

моя оптимизация

Код:
	; Определяем знаки чисел
	If Asc(a) = '-'
    signA = -1
    a = LTrim(a, "-")
	EndIf
	If Asc(b) = '-'
    signB = -1
    b = LTrim(b, "-")
	EndIf

6. упрощение кода:

Код:
Procedure.s String(char.s, count)
	Protected result.s = ""
	For i = 1 To count
    result + char
	Next
	ProcedureReturn result
EndProcedure

оптимизация

Код:
Debug LSet(char.s, count, char.s)
PSY написал(а):

Вот кусок присоединия точки в число, в нём что-то не так

а почему должно быть не так здесь? Здесь только вставка точки, но она могла быть ранее не верно определена, то есть значение totalDecimalPlaces неверно.
Вместо +1 я сделал +2 и стало решать правильно. С позициями всегда так.

Код:
	If aPoint
    a = RemoveString(a, ".")
    aDecimalPlaces = Len(a) - aPoint + 2
	Else
    aDecimalPlaces = 0
	EndIf
	
	If bPoint
    b = RemoveString(b, ".")
    bDecimalPlaces = Len(b) - bPoint + 2
	Else
    bDecimalPlaces = 0
	EndIf

Итоговый (ещё куча изменений: константы вместо строки, устранение циклов и т.д.), проще сравнить в WinMerge, чтобы увидеть все изменения.

Код:
EnableExplicit
#subtract = 2
#subtract_reverse = 3

Procedure DetermineSign(a.s, b.s, operation)
	Protected signA = 1
	Protected signB = 1

	; Определяем знаки чисел
	If Asc(a) = '-'
    signA = -1
    a = LTrim(a, "-")
	EndIf
	If Asc(b) = '-'
    signB = -1
    b = LTrim(b, "-")
	EndIf

	; Определяем знак результата в зависимости от операции
	Select operation
    Case '+'
    	If signA = signB
        ProcedureReturn signA
    	Else
        If signA = 1
        	ProcedureReturn #subtract
        Else
        	ProcedureReturn #subtract_reverse
        EndIf
    	EndIf
    Case '-'
    	If signA = signB
        If signA = 1
        	ProcedureReturn #subtract
        Else
        	ProcedureReturn #subtract_reverse
        EndIf
    	Else
        ProcedureReturn signA
    	EndIf
    Case '*', '/'
    	ProcedureReturn signA * signB
	EndSelect
EndProcedure

Declare.s AddLongNumbers(a.s,b.s)

Procedure.s SubtractLongNumbers(a.s, b.s)
	Protected signResult = DetermineSign(a, b, '-')

	; Убираем знаки из чисел
	If Asc(a) = '-'
    a = LTrim(a, "-")
	EndIf
	If Asc(b) = '-'
    b = LTrim(b, "-")
	EndIf

	; Если знак результата требует сложения
	If signResult = 1 Or signResult = -1
    ProcedureReturn AddLongNumbers(a, b)
	EndIf

	; Выполняем вычитание
	Protected borrow
	Protected result.s
	Protected i, diff, digitA, digitB

	; Выравниваем числа по десятичной точке
	Protected aPoint = FindString(a, ".")
	Protected bPoint = FindString(b, ".")

	If aPoint = 0
    a + ".0"
    aPoint = Len(a) - 1
	EndIf
	If bPoint = 0
    b + ".0"
    bPoint = Len(b) - 1
	EndIf

	; Выравниваем дробные части
	Protected tmp
	tmp = (Len(b) - bPoint) - (Len(a) - aPoint)
	If tmp > 0
    a = LSet(a, Len(b) - bPoint + aPoint, "0")
	ElseIf tmp < 0
    b = LSet(b, Len(a) - aPoint + bPoint, "0")
	EndIf

	; Выравниваем целые части (дробные уже равны, то сразу ровняем всё число)
	If aPoint < bPoint
    a = RSet(a, Len(b), "0")
    aPoint = bPoint
	ElseIf bPoint < aPoint
    b = RSet(b, Len(a), "0")
    bPoint = aPoint
	EndIf

	Protected LenA

	LenA = Len(a) ; чтобы не вычислять длину в каждой итерации
	; Вычитаем цифры справа налево
	For i = LenA To 1 Step -1
    If Mid(a, i, 1) = "."
    	result = "." + result
    	Continue
    EndIf

    digitA = Val(Mid(a, i, 1)) - borrow
    digitB = Val(Mid(b, i, 1))

    If digitA < digitB
    	digitA + 10
    	borrow = 1
    Else
    	borrow = 0
    EndIf

    diff = digitA - digitB
    result = Str(diff) + result
	Next

	; Убираем ведущие нули
	result = LTrim(result, "0")
	If Asc(result) = 0 Or Asc(result) = '.'
    result = "0" + result
	EndIf

	; Добавляем знак результата
	If signResult = -1
    result = "-" + result
	EndIf

	ProcedureReturn result
EndProcedure

Procedure.s AddLongNumbers(a.s, b.s)
	Protected signResult = DetermineSign(a, b, '+')

	; Убираем знаки из чисел
	If Asc(a) = '-'
    a = LTrim(a, "-")
	EndIf
	If Asc(b) = '-'
    b = LTrim(b, "-")
	EndIf

	; Если знак результата требует вычитания
	If signResult = #subtract
    ProcedureReturn SubtractLongNumbers(a, b)
	ElseIf signResult = #subtract_reverse
    ProcedureReturn SubtractLongNumbers(b, a)
	EndIf

	; Выполняем сложение
	Protected carry
	Protected result.s
	Protected i, j, sum, digitA, digitB

	; Выравниваем числа по десятичной точке
	Protected aPoint = FindString(a, ".")
	Protected bPoint = FindString(b, ".")

	If aPoint = 0
    a + ".0"
    aPoint = Len(a) - 1
	EndIf
	If bPoint = 0
    b + ".0"
    bPoint = Len(b) - 1
	EndIf

	; Выравниваем дробные части
	Protected tmp
	tmp = (Len(b) - bPoint) - (Len(a) - aPoint)
	If tmp > 0
    a = LSet(a, Len(b) - bPoint + aPoint, "0")
	ElseIf tmp < 0
    b = LSet(b, Len(a) - aPoint + bPoint, "0")
	EndIf

	; Выравниваем целые части (дробные уже равны, то сразу ровняем всё число)
	If aPoint < bPoint
    a = RSet(a, Len(b), "0")
    aPoint = bPoint
	ElseIf bPoint < aPoint
    b = RSet(b, Len(a), "0")
    bPoint = aPoint
	EndIf

	Protected LenA

	LenA = Len(a) ; чтобы не вычислять длину в каждой итерации
	; Складываем цифры справа налево
	For i = LenA To 1 Step -1
    If Mid(a, i, 1) = "."
    	result = "." + result
    	Continue
    EndIf

    digitA = Val(Mid(a, i, 1))
    digitB = Val(Mid(b, i, 1))

    sum = digitA + digitB + carry
    carry = sum / 10
    result = Str(sum % 10) + result
	Next

	If carry > 0
    result = Str(carry) + result
	EndIf

	; Добавляем знак результата
	If signResult = -1
    result = "-" + result
	EndIf

	ProcedureReturn result
EndProcedure


Procedure.s MultiplyLongNumbers(a.s, b.s)
	Protected signResult = DetermineSign(a, b, '*')
	Protected aDecimalPlaces, bDecimalPlaces

	; Убираем знаки из чисел
	If Asc(a) = '-'
    a = LTrim(a, "-")
	EndIf
	If Asc(b) = '-'
    b = LTrim(b, "-")
	EndIf

	; Убираем десятичные точки и запоминаем количество знаков после точки
	Protected aPoint = FindString(a, ".")
	Protected bPoint = FindString(b, ".")

	If aPoint
    a = RemoveString(a, ".")
    aDecimalPlaces = Len(a) - aPoint + 2
	Else
    aDecimalPlaces = 0
	EndIf

	If bPoint
    b = RemoveString(b, ".")
    bDecimalPlaces = Len(b) - bPoint + 2
	Else
    bDecimalPlaces = 0
	EndIf

	; Умножаем числа как целые
	Protected result.s = "0"
	Protected i, j, carry, product
	Protected temp.s
	Protected LenA, LenB

	LenB = Len(b) ; чтобы не вычислять длину в каждой итерации
	LenA = Len(a)

	For i = LenB To 1 Step -1
    carry = 0
    temp = ""

    For j = LenA To 1 Step -1
    	product = Val(Mid(a, j, 1)) * Val(Mid(b, i, 1)) + carry
    	carry = product / 10
    	temp = Str(product % 10) + temp
    Next

    If carry > 0
    	temp = Str(carry) + temp
    EndIf

    ; Сдвигаем результат влево на соответствующее количество разрядов
    temp + LSet("0", Len(b) - i, "0")
    result = AddLongNumbers(result, temp)
	Next

	; Вставляем десятичную точку
	Protected totalDecimalPlaces = aDecimalPlaces + bDecimalPlaces
	If totalDecimalPlaces
    ; Если количество десятичных разрядов больше длины результата, добавляем ведущие нули
    If totalDecimalPlaces > Len(result)
    	result = LSet("0", totalDecimalPlaces - Len(result), "0") + result
    EndIf
    ; Вставляем точку
    result = Left(result, Len(result) - totalDecimalPlaces) + "." + Right(result, totalDecimalPlaces)
	EndIf

	; Убираем ведущие нули
	result = LTrim(result, "0")
	If Asc(result) = 0 Or Asc(result) = '.'
    result = "0" + result
	EndIf

	; Убираем лишние нули после точки
	If FindString(result, ".")
    result = RTrim(result, "0")
    result = RTrim(result, ".")
	EndIf

	; Добавляем знак результата
	If signResult = -1
    result = "-" + result
	EndIf

	ProcedureReturn result
EndProcedure

Define a.s, b.s
; a = "2.5"
; b = "2.5"
; a = "0.5"
; b = "0.5"
a = "123.456"
b = "78.98765"
; a = "10"
; b = "7"
; a = "0" ; нужна защита от "-0"
; b = "-1"

; Debug "Произведение кодом: " + MultiplyLongNumbers(a, b)
; Debug "Произведе.. PureBasic: " + StrD(ValD(a) * ValD(b))
Debug MultiplyLongNumbers(a, b)
Debug ValD(a) * ValD(b)

Отредактировано AZJIO (09.02.2025 04:11:32)

0

5

Azjio, давайте тогда дошибём и деление раз это работает у вас, я пока что не проверял что тут, а я дошибу длинную степень, логарифм, экспоненту, синус и косинус и прочее.

0

6

PSY написал(а):

судя по названию bigINT INTEGER - это же целые числа, а мне надо с плавающей запятой.

смотря на код как там выравниваются ширина числа, мне не понятно, разве нельзя сделать без этого? Можно даже получить ширину десятичных знаков для чисел 123.456 и 78.98765 это 3+5=8, потом удаляем точку перемножаем как целые числа, потом возвращаем точку на 8. То есть мы как бы умножили числа на 100 миллионов, потом после перемножения разделили на 100 миллионов. И тогда даже bigint возвращает свою актуальность.

В функции перемножение ещё сделал пробу, заменив код

Код:
	Protected LenA, LenB

	LenB = Len(b) ; чтобы не вычислять длину в каждой итерации
	LenA = Len(a)

	For i = LenB To 1 Step -1
    carry = 0
    temp = ""

    For j = LenA To 1 Step -1
    	product = Val(Mid(a, j, 1)) * Val(Mid(b, i, 1)) + carry
    	carry = product / 10
    	temp = Str(product % 10) + temp
    Next

    If carry > 0
    	temp = Str(carry) + temp
    EndIf

    ; Сдвигаем результат влево на соответствующее количество разрядов
    temp + LSet("0", Len(b) - i, "0")
    result = AddLongNumbers(result, temp)
	Next

заменив на

Код:
	Protected LenA, LenB
	Protected *a0, *a.Character, *b.Character

	LenB = Len(b) ; чтобы не вычислять длину в каждой итерации
	LenA = Len(a)
	
	
	*b = @b + LenB * 2 - 2
	*a0 = @a + LenA * 2 - 2

	For i = LenB To 1 Step -1
    carry = 0
    temp = ""
    *a = *a0

    For j = LenA To 1 Step -1
    	product = (*a\c - 48) * (*b\c - 48) + carry
    	carry = product / 10
    	temp = Str(product % 10) + temp
    	*a - 2
    Next

    If carry > 0
    	temp = Str(carry) + temp
    EndIf

    ; Сдвигаем результат влево на соответствующее количество разрядов
    temp + LSet("0", Len(b) - i, "0")
    result = AddLongNumbers(result, temp)
    *b - 2
	Next

Мне показалась такая комбинация

Код:
Val(Mid(a, j, 1))

медленнее чем

Код:
*a\c - 48

Потом увидев функцию AddLongNumbers() я понял что и там надо менять такой же цикл.

Я тут погуглил и нашёл статью с алгоритмами умножения. Наверно проще идти по проложенному пути. Мне понравилось делить число по 6 чисел и перемножать их как quad, это быстрей чем столбиками по числу, а потом складывать с учётом их разрядов. Хотя в quad можно умножать по миллиардам, по 9-значным числам, вот мой пример.

Отредактировано AZJIO (09.02.2025 09:13:51)

0

7

Уже было

0

8

было со сторонней библиотекой, а тут дело в том чтобы такое самому написать

0

9

PSY написал(а):

было со сторонней библиотекой, а тут дело в том чтобы такое самому написать

Дерзай. Хочется посмотреть на реализацию умножения и деления

0


Вы здесь » PureBasic - форум » OpenSource » Работа с длинными числами