Автор Тема: [Все] Первая цифра числа  (Прочитано 19092 раз)

0 Пользователей и 2 Гостей просматривают эту тему.

Оффлайн Kaster [?]

  • Бритва, Бритва Оккама
  • Глобальный модератор
  • *
  • Сообщений: 4020

  • Автор темы
  • Репутация: 622
  • Пол: Мужской
  • Мой Аватар, он лучший самый
    • Награды
  • Версия AutoIt: 3.3.14.0
Re: [Все] Первая цифра числа
« Ответ #15, Отправлен: Март 08, 2012, 22:16:18 »
C2H5OH
умно, умно :) экономит пару операций по сравнению с моим методом и соответственно на пару миллисекунд быстрее на числах 4000-5000. вобщем, победил, молодец  :ok: к сожалению победителей нет
вот сравнительные тест двух методов
Код: AutoIt [Выделить]
$total_my = 0
$total = 0
$NTry = 1000

For $i = 1 to $NTry
    $N = Random(4000, 5000, 1)
    $start = TimerInit()
    FirstDigit($N)
    $total_my += TimerDiff($start)
    $start = TimerInit()
    C2H5OH($N)
    $total += TimerDiff($start)
Next
ConsoleWrite('Average time of my method:' & @TAB & @TAB & $total_my/$NTry & ' msecs' & @CRLF)
ConsoleWrite('Average time of other method:' & @TAB & $total/$NTry & ' msecs' & @CRLF)

Func FirstDigit($N)
    $S = 0
    For $i = 1 to $N
        $S += Log10($i)
    Next
    Return Floor(10^Mod($S, 1))
EndFunc

Func Log10($N)
    Return Log($N)/Log(10)
EndFunc

Func C2H5OH($aNumber)
    Local $aRet = 1
    For $i = 1 to $aNumber
        $aRet *= $i
        If $aRet > 10000000 Then $aRet = Floor($aRet / 1000)
    Next
    Return StringLeft($aRet, 1)
EndFunc
 

на моей машине выдало следующее
Average time of my method: 12.5265294890831 msecs
Average time of other method: 9.82166783767211 msecs

Если кому интересно, я использовал свойство логарифма, что логарифм произведения равен сумме логарифмов.

Старший разряд числа находится путем деления на 10 в степени этого разряда. В терминах же логарифма это разность. Если от логарифма отнять наибольший разряд, то останется лишь дробная часть. Так вот 10 этой дробной степени и есть первая цифра. Чисто математический подход.

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

Всем спасибо за участие :)
« Последнее редактирование: Март 08, 2012, 22:45:52 от Kaster »
Конференция посвященная AutoIt на jabber.ru - [email protected]
Как попасть на конференцию читаем тут


Русское сообщество AutoIt

Re: [Все] Первая цифра числа
« Ответ #15 Отправлен: Март 08, 2012, 22:16:18 »

Оффлайн Zaramot [?]

  • AutoIt Гуру
  • *****
  • Сообщений: 1160
  • Репутация: 654
  • Пол: Мужской
  • I ♥ AutoIt
    • Награды
  • Версия AutoIt: 3.3.8.1
Re: [Все] Первая цифра числа
« Ответ #16, Отправлен: Март 08, 2012, 22:22:17 »
Первая цифра факториала числа 7000 - это 8, а его код выдает 7  :whistle:

Оффлайн Kaster [?]

  • Бритва, Бритва Оккама
  • Глобальный модератор
  • *
  • Сообщений: 4020

  • Автор темы
  • Репутация: 622
  • Пол: Мужской
  • Мой Аватар, он лучший самый
    • Награды
  • Версия AutoIt: 3.3.14.0
Re: [Все] Первая цифра числа
« Ответ #17, Отправлен: Март 08, 2012, 22:31:45 »
Zaramot
Действительно. Значит аккумулируется ошибка при обрезке, которая потом дает о себе знать... Поспешил я с выводами :(
Ладно, т.к. я ответ уже дал, будем считать победивших нет :(

Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473
  • Репутация: 331
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
Re: [Все] Первая цифра числа
« Ответ #18, Отправлен: Март 08, 2012, 22:42:12 »
Zaramot прав.
Мой код корректно работает для чисел до 1000.
При бОльших числах факториал растёт быстрее чем я отбрасываю младшие знаки и происходит переполнение.
Так получилось что на 5001 мой код дал правильный результат, просто совпадение.

Честно говоря особо не отлаживал код - мне настолько понравилось решение с логарифмами, что я был уверен, что оно будет победителем.

А решения с MathEx.au3 и BigNum.au3 не понравились.
Время работы кода с логарифмами - N
Время работы кода с математикой на массивах - N*log(N)
казалось бы разница небольшая, но для больших чисел......


« Последнее редактирование: Март 08, 2012, 22:48:27 от C2H5OH »
Рано или поздно все станет понятно, все станет на свои места и выстроится в единую красивую схему, как кружева. Станет понятно, зачем все было нужно, потому что все будет правильно.

Русское сообщество AutoIt

Re: [Все] Первая цифра числа
« Ответ #18 Отправлен: Март 08, 2012, 22:42:12 »

Оффлайн AZJIO [?]

  • VIP
  • *
  • Сообщений: 2712
  • Репутация: 1137
    • мой сайт
    • Награды
  • Версия AutoIt: 3.3.8.1
Re: [Все] Первая цифра числа
« Ответ #19, Отправлен: Март 08, 2012, 22:53:32 »
C2H5OH
У меня сомнения сразу были с обрезкой числа. Любая функция увеличивающаяся в некой прогрессии зависима от долей. К примеру 2 в степени 64, стоит чуть увеличить число, результат будет на несколько порядков выше. BigNum.au3 хоть и меленная но даст точный результат.

Оффлайн winstan [?]

  • Продвинутый
  • ***
  • Сообщений: 406
  • Репутация: 78
  • Пол: Мужской
  • Эксплотатор)
    • Награды
  • Версия AutoIt: 3.3.12.0
Re: [Все] Первая цифра числа
« Ответ #20, Отправлен: Март 08, 2012, 22:54:46 »
Хм не знал что на длинну числового значения есть ограничение :(
Пришлось умножать столбиком)
Код: AutoIt [Выделить]
$val=100

_fac($val)

Func _fac($val)
    Local $ret=1
    For $i=1 to $val
        $ret=ymnozh($ret,$i)
    Next
    ConsoleWrite("Число: "&$val&@CRLF)
    ConsoleWrite("Факториал: "&$ret&@CRLF)
    ConsoleWrite("Первое число: "&StringLeft( $ret,1)&@CRLF)
EndFunc

Func ymnozh($a,$b)

 $a_arry=StringSplit ( $a, "")
 Local $arry[$a_arry[0]+5]
 for $i=1 to $a_arry[0]
     $arry[$a_arry[0]-$i]=$a_arry[$i]*$b
 Next

 for $i=0 to UBound($arry)-2
     If $arry[$i]>9 Then
         $t=$arry[$i]
     $arry[$i]=StringRight($t,1 )
     $arry[$i+1]+=Floor ($t/10)
     EndIf
 Next
 $ret=""
 for $i=0 to UBound($arry)-1
     $ret=$arry[$i]&$ret
 Next
 Return $ret
EndFunc
 

для работы скрипта нелльзя искать фаториал числа меньше 2  :)


Добавлено: Март 08, 2012, 22:55:41
первоя цифра фаториала 5001 получилась 2
« Последнее редактирование: Март 08, 2012, 23:16:00 от winstan »
Помог мой мост? Жми "Полезное сообщение")

я полный "чайник" , но с другой стороный-не пустой.
Каму не трудно кликните по банару(это поднимит мой кирпичек на стене ников)

Оффлайн Kaster [?]

  • Бритва, Бритва Оккама
  • Глобальный модератор
  • *
  • Сообщений: 4020

  • Автор темы
  • Репутация: 622
  • Пол: Мужской
  • Мой Аватар, он лучший самый
    • Награды
  • Версия AutoIt: 3.3.14.0
Re: [Все] Первая цифра числа
« Ответ #21, Отправлен: Март 08, 2012, 23:00:49 »
winstan
медленно. в BigNum как раз столбиком и производят все операции, только в двоичном виде

Оффлайн winstan [?]

  • Продвинутый
  • ***
  • Сообщений: 406
  • Репутация: 78
  • Пол: Мужской
  • Эксплотатор)
    • Награды
  • Версия AutoIt: 3.3.12.0
Re: [Все] Первая цифра числа
« Ответ #22, Отправлен: Март 08, 2012, 23:11:27 »
Kaster  [?]
Цитировать
медленно. в BigNum как раз столбиком и производят все операции, только в двоичном виде
за то работает на любое число до 10000 и то это ограничение из-за разности размеров нового и уже существовавшего массива

Русское сообщество AutoIt

Re: [Все] Первая цифра числа
« Ответ #22 Отправлен: Март 08, 2012, 23:11:27 »

Оффлайн Kaster [?]

  • Бритва, Бритва Оккама
  • Глобальный модератор
  • *
  • Сообщений: 4020

  • Автор темы
  • Репутация: 622
  • Пол: Мужской
  • Мой Аватар, он лучший самый
    • Награды
  • Версия AutoIt: 3.3.14.0
Re: [Все] Первая цифра числа
« Ответ #23, Отправлен: Март 08, 2012, 23:12:33 »
winstan
я понял что работает, тут рабочих несколько вариантов, если посмотришь. нужен наибыстрейший вариант. а это с логарифмами, который работает хоть до тыщамильонов. ты тему читал?  :)

Оффлайн C2H5OH [?]

  • Знаю я тут одно место с офигенными циркулями...
  • AutoIt Гуру
  • *****
  • Сообщений: 1473
  • Репутация: 331
  • Пол: Мужской
    • Награды
  • Версия AutoIt: 3.3.12.0
Re: [Все] Первая цифра числа
« Ответ #24, Отправлен: Март 08, 2012, 23:20:05 »
AZJIO,
я ещё со школы помню задачку: сколькими нулями заканчивается произведение всех чисел от 1 до 100 ?  :think:
Так что не вижу никакой проблемы в том чтобы обрезать младшие нули.

С другой стороны: при умножении числа на 5000, цифры до какого разряда способны оказать влияние на формирование первой цифры? Я решил что 5 цифр вполне достаточно: 10000000/1000  ;D
Повторюсь, особо не усердствовал.  :beer:

Оффлайн AZJIO [?]

  • VIP
  • *
  • Сообщений: 2712
  • Репутация: 1137
    • мой сайт
    • Награды
  • Версия AutoIt: 3.3.8.1
Re: [Все] Первая цифра числа
« Ответ #25, Отправлен: Март 08, 2012, 23:21:13 »
Kaster
Цитировать
хоть до тыщамильонов
На мильоне уже 3 сек, на 10 мильонов уже 37 сек. Думаю на тыщамильонов 3700 сек будет, а это 1 час.

Оффлайн winstan [?]

  • Продвинутый
  • ***
  • Сообщений: 406
  • Репутация: 78
  • Пол: Мужской
  • Эксплотатор)
    • Награды
  • Версия AutoIt: 3.3.12.0
Re: [Все] Первая цифра числа
« Ответ #26, Отправлен: Март 08, 2012, 23:22:45 »
Kaster
Читал, просто так увлёкся созданием своей функции умнжения числа любой длинны на число до 10000, что просто очень хотелось её показать  ;D

Оффлайн dwerf [?]

  • AutoIt Гуру
  • *****
  • Сообщений: 478
  • Репутация: 218
  • Пол: Мужской
  • Использует ArchLinux
    • Награды
Re: [Все] Первая цифра числа
« Ответ #27, Отправлен: Март 09, 2012, 03:18:43 »
Kaster  [?]
Цитировать
Ладно, т.к. я ответ уже дал, будем считать победивших нет
Раз победивших нет, напишу-ка я, что мне рассказал великий гугл.

(нажмите для показа/скрытия)
00110110001000001101000011010011001

Оффлайн Kaster [?]

  • Бритва, Бритва Оккама
  • Глобальный модератор
  • *
  • Сообщений: 4020

  • Автор темы
  • Репутация: 622
  • Пол: Мужской
  • Мой Аватар, он лучший самый
    • Награды
  • Версия AutoIt: 3.3.14.0
Re: [Все] Первая цифра числа
« Ответ #28, Отправлен: Март 13, 2012, 00:59:09 »
dwerf  [?]
Цитировать
Раз победивших нет, напишу-ка я, что мне рассказал великий гугл.
зачтено :) какая-то уж больно хитрая аппроксимация факториального логарифма, но ответ выдает правильный.

Русское сообщество AutoIt

Re: [Все] Первая цифра числа
« Ответ #28 Отправлен: Март 13, 2012, 00:59:09 »

 

Похожие темы

  Тема / Автор Ответов Последний ответ
12 Ответов
4453 Просмотров
Последний ответ Февраль 01, 2012, 22:54:43
от Viktor1703
12 Ответов
4762 Просмотров
Последний ответ Апрель 15, 2012, 11:37:00
от MyBB
3 Ответов
2225 Просмотров
Последний ответ Июнь 13, 2012, 19:03:01
от Yashied
19 Ответов
6246 Просмотров
Последний ответ Июль 03, 2012, 20:07:21
от Garrett
10 Ответов
4589 Просмотров
Последний ответ Сентябрь 28, 2012, 18:43:22
от ArtInt
2 Ответов
2194 Просмотров
Последний ответ Октябрь 21, 2013, 23:53:57
от britanec74
1 Ответов
1612 Просмотров
Последний ответ Март 27, 2014, 17:50:40
от Garrett
13 Ответов
2794 Просмотров
Последний ответ Март 27, 2014, 23:04:36
от alex33
2 Ответов
1603 Просмотров
Последний ответ Май 06, 2014, 21:07:51
от damien2008
0 Ответов
5991 Просмотров
Последний ответ Март 09, 2015, 19:52:38
от goodmax