c++ - (-1) obtain n পাওয়ার সঠিক উপায় কী?




algorithm x86 (5)

অনেক অ্যালগরিদমের জন্য সাধারণত সিরিজের একটি উপাদান হিসাবে গণনা (-1)^n (উভয় পূর্ণসংখ্যার) প্রয়োজন। এটি, একটি ফ্যাক্টর যা বিজোড় n এর জন্য -1 এবং সমান n এর জন্য 1 । একটি সি ++ পরিবেশে, প্রায়শই দেখা যায়:

#include<iostream>
#include<cmath>
int main(){
   int n = 13;
   std::cout << std::pow(-1, n) << std::endl;
}

এর চেয়ে ভাল বা সাধারণ কনভেনশন কী? (অথবা অন্য কিছু),

std::pow(-1, n)
std::pow(-1, n%2)
(n%2?-1:1)
(1-2*(n%2))  // (gives incorrect value for negative n)

সম্পাদনা করুন:

তদ্ব্যতীত, ব্যবহারকারী @ সেভারিনপ্যাপাডাক্স (বৈশ্বিক?) অ্যারে লুকআপের উপর ভিত্তি করে অন্য একটি বিকল্প প্রস্তাব করেছিলেন। এটির আমার সংস্করণটি হ'ল:

const int res[] {-1, 1, -1}; // three elements are needed for negative modulo results
const int* const m1pow = res + 1; 
...
m1pow[n%2]

এটি সম্ভবত প্রশ্ন নিষ্পত্তি করতে যাচ্ছে না তবে নির্গত কোড ব্যবহার করে আমরা কিছু বিকল্প বাতিল করতে পারি।

অপ্টিমাইজেশন ছাড়াই প্রথমে চূড়ান্ত প্রতিযোগীরা হলেন:

   1 - ((n & 1) << 1);

(7 অপারেশন, কোনও মেমরি অ্যাক্সেস নেই)

  mov eax, DWORD PTR [rbp-20]
  add eax, eax
  and eax, 2
  mov edx, 1
  sub edx, eax
  mov eax, edx
  mov DWORD PTR [rbp-16], eax

এবং

   retvals[n&1];

(5 টি অপারেশন, মেমরি - নিবন্ধক? - অ্যাক্সেস)

  mov eax, DWORD PTR [rbp-20]
  and eax, 1
  cdqe
  mov eax, DWORD PTR main::retvals[0+rax*4]
  mov DWORD PTR [rbp-8], eax

অপ্টিমাইজেশনের সাথে এখন (-O3)

   1 - ((n & 1) << 1);

(4 অপারেশন, কোনও মেমরি অ্যাক্সেস নেই)

  add edx, edx
  mov ebp, 1
  and edx, 2
  sub ebp, edx

  retvals[n&1];

(4 টি অপারেশন, মেমরি - নিবন্ধক? - অ্যাক্সেস)

  mov eax, edx
  and eax, 1
  movsx rcx, eax
  mov r12d, DWORD PTR main::retvals[0+rcx*4]

   n%2?-1:1;

(4 টি অপারেশন, কোনও স্মৃতি অ্যাক্সেস নেই)

  cmp eax, 1
  sbb ebx, ebx
  and ebx, 2
  sub ebx, 1

পরীক্ষা here । অর্থপূর্ণ কোড থাকতে আমার কিছু অ্যাক্রোব্যাটিকসের কাছে ছিল যা পুরোপুরি একত্রে চালিত হয় না।

উপসংহার (এখন জন্য)

সুতরাং শেষে এটি স্তরের অপ্টিমাইজেশান এবং ভাব প্রকাশের উপর নির্ভর করে:

  • 1 - ((n & 1) << 1); সর্বদা ভাল তবে খুব ভাবের নয়।
  • retvals[n&1]; মেমরি অ্যাক্সেসের জন্য একটি মূল্য প্রদান করে।
  • n%2?-1:1; অভিব্যক্তিপূর্ণ এবং ভাল তবে কেবল অপটিমাইজেশন সহ।

অনেক অ্যালগরিদমের জন্য সাধারণত সিরিজের একটি উপাদান হিসাবে গণনা (-1) ^ n (উভয় পূর্ণসংখ্যার) প্রয়োজন। এটি, একটি ফ্যাক্টর যা বিজোড় n এর জন্য -1 এবং সমান n এর জন্য 1।

পরিবর্তে -x এর ক্রিয়া হিসাবে সিরিজটি মূল্যায়ন বিবেচনা করুন।


আপনি সুপার-পেডেন্টিক হতে চাইলে আপনি n % 2 পরিবর্তে (n & 1) এবং * 2 << 1 পরিবর্তে << 1 ব্যবহার করতে পারেন, এর অর্থ আমি অনুকূলিত।
সুতরাং ৮০86 process প্রসেসরের গণনা করার দ্রুততম উপায় হ'ল:

1 - ((n & 1) << 1)

আমি কেবল এই উত্তরটি কোথা থেকে আসছে তা স্পষ্ট করতে চাই। মূল পোস্টার আলএফসি গণনা করার জন্য বিভিন্ন পদ্ধতিতে (-1) বিভিন্ন পোস্ট করার একটি দুর্দান্ত কাজ করেছে ^ n কিছু অন্যের তুলনায় দ্রুত।
আজকাল প্রসেসরগুলি যত তাড়াতাড়ি দ্রুত গতিতে এবং সংকলকগুলি তারা তত উন্নত হওয়ার জন্য আমরা সাধারণত কোনও অপারেশন থেকে কয়েকটি সিপিইউ চক্র শেভ করার মধ্য থেকে সামান্য (এমনকি তুচ্ছ) উন্নয়নের চেয়েও পঠনযোগ্যতার মূল্যায়ন করি।
এমন একটি সময় ছিল যখন একটি পাস সংকলক পৃথিবীতে রাজত্ব করত এবং এমএলইউর অপারেশনগুলি নতুন এবং ক্ষয়িষ্ণু ছিল; এই দিনগুলিতে 2 অপারেশনের শক্তি হ'ল কৃত্রিম অপ্টিমাইজেশনের জন্য একটি আমন্ত্রণ।


ঠিক আছে, আমরা যদি একটি সিরিজে গণনা সম্পাদন করি, তবে কেন মূল্যায়ন পুরোপুরি বাদ দিয়ে একটি ধনাত্মক লুপ এবং নেতিবাচক লুপে গণনাটি পরিচালনা করবেন না?

প্রাকৃতিক লগের আনুমানিক টেলর সিরিজ সম্প্রসারণ (1 + x) এই ধরণের সমস্যার এক নিখুঁত উদাহরণ। প্রতিটি পদে (-1) ^ (n + 1), বা (1) ^ (n-1) রয়েছে। এই ফ্যাক্টরটি গণনা করার দরকার নেই। আপনি প্রতি দুটি পদে 1 টি লুপ, বা দুটি লুপ, বিজোড় পদগুলির জন্য একটি এবং এমনকি এমনকি শর্তাদির জন্য একটি কার্যকর করে সমস্যাটি "টুকরো টুকরো" করতে পারেন।

অবশ্যই গণনাটি প্রকৃতি অনুসারে প্রকৃত সংখ্যার ডোমেনের এক, সুতরাং আপনি পৃথক পদগুলি যেভাবেই মূল্যায়ন করতে ভাসমান পয়েন্ট প্রসেসর ব্যবহার করবেন। একবার আপনি এটি করার সিদ্ধান্ত নিলে, আপনার কেবলমাত্র প্রাকৃতিক লগারিদমের জন্য লাইব্রেরি প্রয়োগটি ব্যবহার করা উচিত। তবে যদি কোনও কারণে, আপনি না নেওয়ার সিদ্ধান্ত নেন তবে এটি অবশ্যই দ্রুততর হবে তবে খুব বেশি নয়, নবম শক্তি থেকে -1 এর মান গণনা করা চক্রটি নষ্ট করবেন না।

সম্ভবত প্রতিটি পৃথক থ্রেডেও করা যেতে পারে। এমনকি সমস্যাটি ভেক্টরাইজড হতে পারে, এমনকি।


প্রথমত, আমি জানি সবচেয়ে দ্রুততম আইডড পরীক্ষা (একটি ইনলাইন পদ্ধতিতে)

/**
* Return true if the value is odd
* @value the value to check
*/
inline bool isOdd(int value)
{
return (value & 1);
}

তারপরে এই পরীক্ষারটি বিজোড় হলে -1 ফেরত দিতে ব্যবহার করুন, অন্যথায় 1 (যা (-1) actual N এর প্রকৃত আউটপুট)

/**
* Return the computation of (-1)^N
* @n the N factor
*/
inline int minusOneToN(int n)
{
return isOdd(n)?-1:1;
}

সর্বশেষে @ গুভান্টের পরামর্শ অনুসারে, আপনি কোনও মানের চিহ্নটি উল্টিয়ে একটি গুণকে বাঁচাতে পারবেন (মাইনাসঅনটোন ফাংশনটি ব্যবহার করা এড়ানো)

/**
* Example of the general usage. Avoids a useless multiplication
* @value The value to flip if it is odd
*/
inline int flipSignIfOdd(int value)
{
return isOdd(value)?-value:value;
}

সাধারণত আপনি প্রকৃতপক্ষে (-1)^n গণনা করেন না, পরিবর্তে আপনি বর্তমান চিহ্নটি (একটি সংখ্যা হিসাবে -1 বা 1 হচ্ছেন) ট্র্যাক করেন এবং এটি প্রতিটি ক্রিয়াকলাপটি sign = -sign করে ( sign = -sign ), আপনি যখন আপনার sign = -sign পরিচালনা করেন তখন এটি করুন ক্রম এবং আপনি একই ফলাফল পাবেন।

সম্পাদনা: যে কারণে আমি এটির প্রস্তাব দিচ্ছি তার একটি অংশটি নোট করুন কারণ সেখানে বিরল প্রকৃতপক্ষে খুব কমই উপস্থিতি রয়েছে (-1)^n it (-1)^n এটি কেবল পুনরাবৃত্তির মধ্যে চিহ্নটি উল্টানোর সুবিধামত পদ্ধতি।





cmath