Число в строку (NASM/YASM)

[BratSinot]

Доброго времени суток!

Имеем число X, где X принадлежит множеству натуральных чисел. Нужно вывести это число на экран.
Я знаю только как вывести либо символ, либо строку на экран. Если 9>X>1, то все просто, прибавляем 48('0' в ASCII) и выводим как символ. А если скажем X=123? Единственная мысль которая мне приходит, очень плохая мысль, это перевести это число в строку. Перевод я вижу примерно так:

Код: Выделить всё

Узнаем кол-во цифр==COL, делим число на 10 (COL-1) раз. Таким образом мы узнаем первую цифру. К ней прибавляем 48 и добавляем в строку и так до победного.

В этом алгоритме меня не устраивает его громоздскойсть. Операция деления происходит за несколько тактов. А если число будет (2^64-1), то это будет ну очень много тактов, а это еще без учета вывода на экран каждого символа.

Есть ли более простые способы вывода на экран? Я сейчас для проверки решения поставленных задач, вызываю printf из libc, но я хотел бы сделать это посредством вызова системных вызовов.
P.S. Использую YASM, инструкции можно использовать с i*86 и amd64.
P.S.S. Соотвественно пишу под GNU/Linux, но можно и под другие *nix, можно будет попытаться разобраться.
P.S.S.S. Я не студент.

[NickLion]

2^64-1 - это не более 19 цифр ==> не более 19 делений, неужели так много? Делите и не "парьтесь", всё равно ничего лучше нет. И Вы правильно заметили, что вывод будет занимать значительно больше времени, чем деление. Так что не занимайтесь оптимизациями, которые не принесут профита.

[BratSinot]

2^64-1 - это не более 19 цифр ==> не более 19 делений, неужели так много?

Это просто дофига. 19 раз поделить, отчленить цифру, прибавить, вывести. Примерно прикинем деление 4 такта, "отчленение" скажем два такта, прибавка 1 такта, вывод 10 тактов. Итого (4+1+10)*19==285 тактов. Это ну очень много, для какой-то жалкой операции вывода.

Делите и не "парьтесь", всё равно ничего лучше нет.

Напомню про такое понятие как алгоритм. Если деление единственный вариант, то мой вариант основанный на делении очень кривой.

И да, наврятли только делениями.

[Nazyvaemykh]

У Кнута несколько алгоритмов приводится, смотрели?
Хотя вот ужь не думаю, что если «железка» тянет на себе такую раздутую вещь как GNU\Linux, то операция вывода может быть сколько-нибудь существенно обременительной.

[BratSinot]

У Кнута несколько алгоритмов приводится, смотрели?

У какого Кнута?

Хотя вот ужь не думаю, что если «железка» тянет на себе такую раздутую вещь как GNU\Linux, то операция вывода может быть сколько-нибудь существенно обременительной.

Давайте вспомним 1991 год, это раз. Я не из Мелкософта, это два. Смысл писать на языке ассемблера неоптимизированные программы?

Да и потом, процесс с делением надо будет повторять кучу раз. Сначала чтоб узнать кол-во символов, потом чтоб узнать каждый следующий + еще вычитать нужно будет.

[sgfault]

У Кнута несколько алгоритмов приводится, смотрели?

У какого Кнута?

(не нашлось тут у вас более подходящих смайлов ^)

Давайте вспомним 1991 год

Зачем его вспоминать, он больше никогда не настанет. Лучше подумайте о 2091

Я не из Мелкософта, это два.

А вы и правда думаете, что там плохие программисты? Эх..

ЗЫ. Флуд, конечно, но не удержался, сори

[BratSinot]

А вы и правда думаете, что там плохие программисты? Эх..

А кто говорил про плохих, хороших? Я про политику говорил.

[sash-kan]

У какого Кнута?

вот и выросло поколение программистов, считающих, что кнут — это имя либо белого медведя, сдохшего недавно в берлинском зоопарке, либо английского короля из рода кнютлингов·
википедия://Дональд Кнут

[BratSinot]

вот и выросло поколение программистов, считающих, что кнут — это имя либо белого медведя, сдохшего недавно в берлинском зоопарке, либо английского короля из рода кнютлингов·

Либо ничего не думают. И откуда мне его знать? В советских книгах про США наврятли чего будет, а в школе явно такому учить не будут.
P.S. Мне еще далековато до понятия "вырос".
А за разъяснение спасибо.

[RasenHerz]

Это просто дофига. 19 раз поделить, отчленить цифру, прибавить, вывести. Примерно прикинем деление 4 такта, "отчленение" скажем два такта, прибавка 1 такта, вывод 10 тактов. Итого (4+1+10)*19==285 тактов. Это ну очень много, для какой-то жалкой операции вывода.

Вот только запись в файл требует переключения контекста (юзерспейс -> кернелспейс -> юзерспейс), а это огромное количество тактов (тысячи, а может и десятки или сотни тысяч тактов), так что не стоит выдумывать сверхбыстрый алгоритм для данной задачи - операция ввода/вывода займет не сопоставимо больше времени чем преобразование числа в строку.

P.S. И это без учета потерь в libc (если таковая используется для вывода), а также возможности вытеснения процессов в ядре (что в принципе не сказывается на количестве тактов необходимых для выполнения программы, но сказывается на общем времени ее исполнения).
P.P.S. А вывод таков: не стоит усложнять решение простых задач.

[BratSinot]

P.S. И это без учета потерь в libc (если таковая используется для вывода)

Сами подумайте, если используется libc, то на кой чер нужно делать перевод в строку?

P.P.S. А вывод таков: не стоит усложнять решение простых задач.

... А я чем занимаюсь? Пытаюсь упростить.

[sash-kan]

на всякий случай добавлю, что когда говорят «посмотрите у кнута», подразумевают его фундаментальный труд википедия://искусство программирования·

[RasenHerz]

P.S. И это без учета потерь в libc (если таковая используется для вывода)

Сами подумайте, если используется libc, то на кой чер нужно делать перевод в строку?

Я сейчас для проверки решения поставленных задач, вызываю printf из libc, но я хотел бы сделать это посредством вызова системных вызовов.

Ну да ладно с этой libc, ответьте мне лучше сколько тактов вы потеряете во время переключений контекста исполнения, которые непременно произойдут после системного вызова.

[NickLion]

BratSinot, поймите, Вы не то пытаетесь оптимизировать. Банальное обращение к памяти может "подвесить" поток тактов на 150, если мимо кэша. А если страница не в памяти, а в свопе, то ещё хуже. Вывод строки за счёт переключений контекста (как уже говорили) тоже очень сильно испортит время. ТАк что не в делении проблема.

[drBatty]

В этом алгоритме меня не устраивает его громоздскойсть.

более простой вариант:
1)получить последнюю цифру как x%10.
2)получить x<=x/10
Только цифры получаются наоборот.

алгоритм А: печать посл. цифры
1) если x>=10 вызываем алгоритм А для x/10
2) если x < 10 просто печатаем.

[BratSinot]

1)получить последнюю цифру как x%10.
2)получить x<=x/10

Спасибо!

[drBatty]

У какого Кнута?

Я не из Мелкософта, это два.

вижу. иначе-бы знали, что у Кнута есть задачки в его книжке, и если их все решить, то вы уже работник мысы - БГ гарантирует это! ;)

(БГ тут не наш Гуру с бородой)

Спасибо!

нзч. это рекурсия - удивительно полезный инструмент. Но лучше к Кнуту, он хорошо пишет.
http://www.ozon.ru/context/detail/id/1335648/
ну и далее. Надо мне новый томик прикупить в коллекцию... (кстати, эта книжка есть у любого кодера).

[BratSinot]

А насчет задом наперед решается легко. Пихаем в стек и соответствено выводим из него.

[drBatty]

А насчет задом наперед решается легко. Пихаем в стек и соответствено выводим из него.

а я так и сделал, содержимое стека в момент, когда мы печатаем 1 из 12345

Код: Выделить всё

12345
адр. возврата
1234
а.в.
123
а.в.
12
а.в
1 <--- эту локальную x мы и печатаем

[NickLion]

drBatty
BratSinot
Я чего-то не понял. Пришли к тому, что говорили с самого начала - делим. 19 цифр - 19 делений. Ничего не понимаю.

[taaroa]

делим. 19 цифр - 19 делений.

одепт, помни! div — очень медленная операция.

[drBatty]

Я чего-то не понял. Пришли к тому, что говорили с самого начала - делим. 19 цифр - 19 делений. Ничего не понимаю.

да. деление занимает несколько тактов, что по сравнению с выводом ==0.
Если вам нечем заняться - замените деление на умножение. например, для 16и бит это 1/10 == 65536/10*65536. деление сделайте на калькуляторе, а умножение сдвигами. в асме х86 это просто использование DX вместо AX.

одепт, помни! div — очень медленная операция.

с разморозкой :)

[NickLion]

да. деление занимает несколько тактов, что по сравнению с выводом ==0.

Да я как-то изначально говорил, что надо делить - это самый верный способ.

Если вам нечем заняться - замените деление на умножение. например, для 16и бит это 1/10 == 65536/10*65536. деление сделайте на калькуляторе, а умножение сдвигами. в асме х86 это просто использование DX вместо AX.

Эм... Я думаю, что на 10 разделить я и в уме смогу. К тому же неболшая ошибочка - деление сдвигами.
1/10=65536/(10*65536)=6553 / 65536. Но тут же вещественная часть пропадает. И остаток умножен на 6553 - придётся ещё столько городить (с условиями!) что проще таки делить. Быстрее.

[BratSinot]

Во! Еще кой чего придумал, мы когда в cтек загоняем получаем типо строку, и дальше выводим не посимвольно, а строкой.
Если интерсно, то выглядит это так:

Код: Выделить всё

    mov eax, 123456789

    mov EBX, 10
    mov ECX, ESP
.again:
    xor EDX, EDX
    div EBX
    add EDX, 48
    mov [ESP], DL
    dec ESP
    test EAX, EAX
    jne short .again

    inc ESP
    sub ECX, ESP

    mov EDX, ECX    ; amount of data
    mov EAX, 4      ; 'write' syscall
    mov EBX, 1      ; file descr. 1 (stdout)
    mov ECX, ESP    ; pointer to the data
    int 0x80        ; call to the kernel

Разница в скорости на 734%!