pow가 O(1)이 아니면 덧셈 곱셈 나눗셈도 O(1)아니다

[익명(182.224)]

학부때 얼마나 개 좆으로배웠으면

pow가 O(1)이 아니래?

그딴 논리면 덧셈뺄셈곱셈나눗셈 싹다 O(1)아니라는건데

공부안하고 뭐했노

[익명(118.39)]

이게맞지 ㅋㅋㅋ

[익명(118.39)]

이게맞지 ㅋㅋㅋㅋ

[익명(118.39)]

이게맞지 ㅋㅋㅋㅋ

[익명(118.39)]

이게 맞지 ㅋㅋㅋㅋ

[익명(58.230)]

O(1) 아닌거 이제 알았냐?

[익명(182.224)]

초졸티내지마라

[익명(58.230)]

현존하는 정수 곱셈 알고리즘 중에서 가장 빠른 게 n자리에 대해 O(n log n)임 ㅇㅇ 올해 발표된 거

[익명(182.224)]

논문 가져와보셈

[익명(106.102)]

ㅋㅋㅋㅋ

[익명(58.230)]

https://hal.archives-ouvertes.fr/hal-02070778/document

[익명(1.240)]

fft 쓰면 nlogn ㅅㄱ

[나트륨찡(alphauri)]

저 논문 e^2pi ij/n 뜨는 거 보니 걍 fft쟈나 복소수 연산으로 정수곱셈하는 게 컴퓨터에서만 가능한 거지 nlogn 은 원래 fft로도 가능했음

[나트륨찡(alphauri)]

내가 원하는 건 정수론 곱셈임

[나트륨찡(alphauri)]

실수 연산 없이 정수론 연산을 달라구

[익명(58.230)]

?? 뜬금없이 뭔 소린지 모르겠네

[익명(58.230)]

정수로만 계산하고싶으면 쇤하게 슈트라센같은 걸 찾아보든지. 내가 알기론 O(n log n) 곱셈은 저게 최초임.

[나트륨찡(alphauri)]

슈트라센은 O(nlognloglogn)인가 그랫을 거임 나도 원래 알고 있던 거고 O(nlogn)을 계산하는 게 저 논문 처럼 실수랑 복소수 활용할 거면 fft와 다를 바 없는 거고 복소수+실수계산인 fft로는 곱셈 이미 O(nlogn)으로 간단하게 분할정복으로 풂 학부 때 fft로 배우지 않나

[나트륨찡(alphauri)]

저거 다시 보니까 행렬에 실수 e-10이딴 거 빼곡하게 적혀있는 거 보니까 정수론 계산 아니고 실수 계산인데 이거는 fft와 다를 바 없는 거고 내가 말했던 건 O(nlogn) 정수론 계산이 아직 안나왔다는 거임 실수계산할 거면 어차피 fft로 O(nlogn)으로 훨씬 간단하고 일반적인 방법으로 풀림 fft@ convolution 찾아보셈

[나트륨찡(alphauri)]

다시 확인하려고 fft 검색해보니 fft가 O(nlogn) 맞네 그리고 fft가 간단하고 일반적인 방법으로 곱셈을 O(nlogn) 푸는 방법임 이름에 괜히 fast가 붙은 게 아님

[익명(58.230)]

;; 뭐 그렇다 치고 그거랑 이 글이랑 뭔 연관이 있음?

[익명(58.230)]

정수론 계산을 하고싶으면 니가 알아서 찾아보던가 ㅋㅋ 왜 이상한 글에 와서 내놓으라고 요구하는건지 모르겠다

[익명(123.212)]

정보)나눗셈은 곱셈보다 느리다

[익명(1.240)]

문제 정의가 문제지 병신아; 곱셈도 기본 자료형 수준 넘으면 카라츠바 쓰면 n^(log3)이고 fft 쓰면 nlogn인건 알고 있지? 개소리 지껄이기 전에 제발 CLRS라도 읽고 와라

[tof51(tof99)]

무슨말인지 잘 모르지만, 자바에서 배열이 0부터 시작하고, 어디서는 1부터 시작하고.. 프로그래밍언어자체 이야기 같은데.

[17번(wjd918273)]

그거아님 - dc App

[tof51(tof99)]

수학 증명이야기인가.. 그런 생각 드네요. 댓글, 감사합니다.